数据结构中的哈夫曼树-考研重点
哈夫曼树是考研中的必考内容之一，哈夫曼树是什么？有什么用？
例：编程：将学生百分制成绩转换为五分制成绩 < 60:E 60-69:D 70-79:C 80-89:B 90-100:A
可以直接if else或者switch转换
假设成绩分布是这样的：
如果每次的输入量很大，则应考虑程序的操作时间
怎么找到效率最高的判定树呢？—> 哈夫曼树(最优二叉树)
哈夫曼树相关的几个名词
路径：在一棵树中，一个结点到另一个结点之间的通路，称为路径。图 1 中，从根结点到结点 a 之间的通路就是一条路径
路径长度：在一条路径中，每经过一个结点，路径长度都要加 1 。例如在一棵树中，规定根结点所在层数为1层，那么从根结点到第 i 层结点的路径长度为 i – 1 。图 1 中从根结点到结点 c 的路径长度为 3。
树的路径长度：从树根到每一个根结点的路径长度之和，记作TL；
补充：结点数目相同的二叉树中，完全二叉树是路径长度最短的二叉树。
结点的权：给每一个结点赋予一个新的数值，被称为这个结点的权。例如，图 1 中结点 a 的权为 7，结点 b 的权为 5。
结点的带权路径长度：指的是从根结点到该结点之间的路径长度与该结点的权的乘积。例如，图 1 中结点 b 的带权路径长度为 2 * 5 = 10 。
树的带权路径长度为树中所有叶子结点的带权路径长度之和。通常记作 “WPL” 。例如图 1 中所示的这颗树的带权路径长度为：
图1 哈夫曼树
计算带权路径长度
哈夫曼树
哈夫曼树：带权路径长度最短的二叉树
由上图我们可以得出几个结论：满二叉树不一定是哈夫曼树哈夫曼树中权越大的叶子离根越近具有相同带权结点的哈夫曼树不唯一
哈夫曼树构造算法
例如：有4个结点a,b,c,d,权值分别为7，5，2，4，构造哈夫曼树；点击查看答案
哈夫曼树算法实现
例：有n=8,权值为w={7,19,2,6,32,3,21,10}
哈夫曼编码
在远程通讯中，要将待传字符转换成由二进制的字符串，设要传送的字符：ABACCDA， 若编码：
编码结果：00010010101100
若将编码设计为长度不等的二进制编码，让待传字符串中出现次数较多的字符采用尽可能短的编码，则转换的二进制字符便可能减少。
000011010
但是上面这个码在转换的时候就会出现问题，以000为例，可能是AB也可能是AAA；原因是A的编码0是B的编码的前缀。
若要设计长度不等的编码，则必须使任一字符的编码都不是另一字符的编码的前缀。这种编码称为前缀码。
什么样的前缀码使得电文总长度最短？
有关哈夫曼树的两个为什么？ 
为什么哈夫曼编码能够保证是前缀编码？因为没有一片树叶是另一片树叶的祖先，所以每个叶子节点的编码就不可能是其他叶子节点的前缀为什么哈夫曼编码能够保证字符编码总长最短？因为哈夫曼树带权路径长度最短，故字符编码的总长最短
哈夫曼编码是最优前缀编码例：设组成电文的字符集D及其概率分布W为： D={A,B,C,D,E,F,G} W={0.40, 0.30, 0.15, 0.05, 0.04, 0.03, 0.03} 设计哈夫曼编码
2024最新激活全家桶教程，稳定运行到2099年，请移步至置顶文章：https://sigusoft.com/99576.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处：https://sigusoft.com/97385.html
