设某赫夫曼树的高度为5,若已对两个字符编码为1和01,则最多还可以对( )个字符编码。

admin2021-08-17  35

问题 设某赫夫曼树的高度为5,若已对两个字符编码为1和01,则最多还可以对(    )个字符编码。

选项 A、3
B、4
C、5
D、6

答案B

解析 首先,赫夫曼编码遵循的原则为:一个编码不能是任何其他编码的前缀。比如1和10就不行,因为1是10的前缀。既然1和01已经使用了,所以1和01开头的码字不能再使用。又由于赫夫曼树的高度为5,故赫夫曼编码的长度不能超过4,只剩下0000、0001、0010、O011等4种编码(这种编码方式可得到最多),故选B选项。
注意:本题选的是最多还可以对多少个字符编码,所以不能选取001、000等编码。例如选取001,就意味着0010和0011不能使用,这样可编码的字符就少了1个。
总结:
(1)有n个叶子结点的赫夫曼树的结点总数为2n—1。
(2)高度为h的赫夫曼树中,至少有2h—1个结点,至多有2h—l个结点。
(3)赫夫曼树中一定没有度为1的结点。
(4)赫夫曼树中两个权值最小的结点一定是兄弟结点。
(5)树中任一非叶子结点的权值一定不小于下一层任一结点的权值。
补充例题:一棵赫夫曼树共有215个结点,对其进行赫夫曼编码,共能得到多少个码字?
解析:求多少个码字就是求有多少个叶结点,从(1)可以得到,叶结点的个数为108个,故可以得到108个码字。
转载请注明原文地址:https://jikaoti.com/ti/7BDjFFFM
0

相关试题推荐
最新回复(0)