关于哈夫曼编码试题的计算

发布网友发布时间：2022-04-23 04:24

共1个回答

热心网友时间：2023-10-14 16:59

太复杂了，楼主一会记得多给我点分！谢谢啦！
先设权w=(31,22,18,14,10,4,1),n=7,则m=13,按照哈夫曼算法可以构造一棵哈夫曼树如下：
100
40 60
22 18 31 29
14 15
10 5
4 1
末端结点为22，18，31，14，10，4，1，你自己把上面的加上线连成一棵二叉树就行，记得左分支标0，右分支标1（为了得出后面的哈夫曼编码HC）
然后需要列出HT初态表和HT终态表，如下：
HT初态表 HT终态表
weight parent lchild rchild weight parent lchild rchild
1 31 0 0 0 31 12 0 0
2 22 0 0 0 22 11 0 0
3 18 0 0 0 18 11 0 0
4 14 0 0 0 14 10 0 0
5 10 0 0 0 10 9 0 0
6 4 0 0 0 4 8 0 0
7 1 0 0 0 1 8 0 0
8 - 0 0 0 5 9 6 7
9 - 0 0 0 15 10 5 8
10 - 0 0 0 29 12 4 9
11 - 0 0 0 40 13 2 3
12 - 0 0 0 60 13 1 10
13 - 0 0 0 100 0 11 12
最后得出哈夫曼编码HC：
1——>10
2——>00
3——>01
4——>110
5——>1110
6——>11110
7——>11111
平均码字长度为（0.31＋0.22＋0.18）×2＋0.14×3＋0.1×4
＋（0.04＋0.01）×5＝2.47
编码效率为[（1－0.01）×3＋0.01×2]/2.47=1.21
解答完毕！
补充：对于其中的编码效率问题本人有点淡忘，我选择的是用
普通平均编码长度除上了哈夫曼平均编码长度得出，不知对否。
辛苦半天，望楼主能赐我分数，不胜感激！
注：提交后发现格式不太规整，对于哈夫曼树谁是谁的左孩子、右孩子比较容易分出（左右孩子结点相加可知父亲结点），对于HT初态表和HT终态表1列1列的看就行！其中数字第一列为序号，从第2列到第9列分别对应HT初态表的weight parent lchild rchild 和HT终态表的weight parent lchild rchild 。