6.6 赫夫曼树及其应用
【摘要】 01最优二叉树（赫夫曼树）1、从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径，路径上的分支数目称做路径长度。2、树的路径长度是从树根到每一结点的路径长度之和。3、结点的带权路径长度为从该结点到树根之间的路径长度与结点上权的乘积。树的带权路径长度为树中所有叶子结点的带权路径长度之和。4、假设有n个权值{w1，w2...wn}，试构造一棵有n个叶子结点的二叉树，每个叶...
01最优二叉树（赫夫曼树）
1、从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径，路径上的分支数目称做路径长度。
2、树的路径长度是从树根到每一结点的路径长度之和。
3、结点的带权路径长度为从该结点到树根之间的路径长度与结点上权的乘积。树的带权路径长度为树中所有叶子结点的带权路径长度之和。
4、假设有n个权值{w1，w2...wn}，试构造一棵有n个叶子结点的二叉树，每个叶子结点带权为wi，则其中带权路径长度WPL最小的二叉树称做最优二叉树或赫夫曼树。
02赫夫曼编码
1、目前，进行快速远距离通信的主要手段是电报，即将需传送的文字转换成由二进制的字符组成的字符串。
2、在传送电文时，希望总长尽可能地短。如果对每个字符设计长度不等的编码，且让电文中出现次数较多的字符采用尽可能短的编码，则传送电文的总长便可减少。
3、若要设计长短不等的编码，则必须是任一字符的编码都不是另一个字符的编码的前缀，这种编码称做前缀编码。
C语言 | 递归求年龄
文章来源: zhuanlan.zhihu.com，作者：小林C语言，版权归原作者所有，如需转载，请联系作者。
原文链接：zhuanlan.zhihu.com/p/337457830
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）