目录
1..赫夫曼树概述
2.计算WPL
1)图示
2)计算
3.计算字符编码
1)图示
2）Huffman编码
1.赫夫曼树概述
HuffmanTree因为翻译不同所以有其他的名字：赫夫曼树、霍夫曼树、哈夫曼树。
赫夫曼树，又称最优数，是一类带权路径长度最短的数，有着广泛的应用。
这里我们提出两个问题加深对最优二叉树的理解。
2.计算WPL
问题：设给定权值集合w={3,5,7,8,11,12}，请构造关于w的一颗huffman树，并求其加权路径长度WPL
1）图示：
构造解释：组合最小的两个数做组合，比如3和5在集合中最小，我们组成的新值为8此时我们由原来的集合变为{8,7,8,11,12}，依次类推。
2）计算
WPL路经长为:叶子结点（也就是没有任何分支的节点）*路径数(就是从上——>下的连线数)。
WPL=12*2+7*3+3*4+5*4+8*2+11*2=115。
3.计算字符编码
问题：假设通信的电文是由字符集{a,b,c,d,e,f,g}中的字符构成，这8个字符在电文中出现的概率分别为{0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10}，求出每个字符的哈夫曼编码。
1)图示:
这里我将概率乘以100%方便观察，然后我们将对应的字母读入二叉树图示如下:
二叉树二进制编码为左0右1
2)Huffman编码:
a:0010
b:10
c:00000
d:0001
e:01
f:00001
g:11
h:0011
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/121335.html