哈夫曼(Huffman)树和哈夫曼编码
标签: 数据结构
学习人数: 10996


全屏播放
赞赏支持

哈夫曼树

基本概念

给定N个权值作为N个叶子结点,构造一棵二叉树,若该树的带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近。

 

概念1:什么是路径?

在一棵树中,从一个结点到另一个结点所经过的所有结点,被我们称为两个结点之间的路径。

上面的二叉树当中,从根结点A到叶子结点H的路径,就是A,B,D,H。

 

概念2:什么是路径长度?

在一棵树中,从一个结点到另一个结点所经过的“边”的数量,被我们称为两个结点之间的路径长度。

仍然用刚才的二叉树举例子,从根结点A到叶子结点H,共经过了3条边,因此路径长度是3。

 

概念3:什么是结点的带权路径长度?

树的每一个结点,都可以拥有自己的“权重”(Weight),权重在不同的算法当中可以起到不同的作用。

结点的带权路径长度,是指树的根结点到该结点的路径长度,...

登录查看完整内容


课后作业

课后习题

 

【2019年真题】对n个互不相同的符号进行哈夫曼编码。若生成的哈夫曼树共有115个结点,则n的值是()
A. 56            B. 57             C. 58            D. 60

参考答案:C

 

【2018年真题】已知字符集 {a, b, c, d, e, f},若各字符出现的次数分别为6, 3, 8, 2, 10, 4,则对应字符集中各字符的哈夫曼编码可能是()。
A . 00, 1011, 01, 1010, 11, 100    B. 00, 100, 110, 000, 0010, 01
C. 10, 1011, 11, 0011, 00, 010    D. 0011, 10, 11, 0010, 01, 000

参考答案:A

 

【2017年真题】已知字符集{a,b,c,d,e,f,g,h},若各字符的哈夫曼编码依次是0100,10,0000,0101,001,011,11,0001,则编码序列0100011001001011110101的译码结果是()
A.a c g a b f h        B.a d b a g b b        C.a f b e a g d        D.a f e e f g d

参考答案:D

 

【2015年真题】下列选项给出的是从根分别到达两个叶结点路径上的权值序列,能属于同一棵哈夫曼树的是()。
A.24,10,5 和 24,10,7        B.24,10,5 和 24,12,7
C.24,10,10 和 24,14,11    D.24,10,5 和 24,14,6

参考答案:D

 

【2014年真题】5 个字符有如下 4 种编码方案,不是前缀编码的是()
A.01,0000,0001,001,1 
B.011,000,001,010,1 
C.000,001,010,011,100 
D.0,100,110,1110,1100

参考答案:D
答案解析:前缀编码的定义是在一个字符集中,任何一个字符的编码都不是另一个字符编码的前缀。D中编码 110 是编码 1100 的前缀,违反了前缀编码的规则,所以 D 不是前缀编码。 

 

【2013年真题】若将关键字 1,2,3,4,5,6,7 依次插入到初始为空的平衡二叉树 T 中,则 T 中平衡因子为 0 的分支结点的个数是()
A. 0             B. 1             C. 2         D. 3

参考答案:D
答案解析:利用 7 个关键字构建平衡二叉树 T,平衡因子为 0 的分支结点个数为 3,构建的平衡 
二叉树如下图所示。


【2010年真题】对 n(n≥2)个权值均不相同的字符构造成哈夫曼树。下列关于该哈夫曼树的叙述中,错误的是()。 
A.该树一定是一棵完全二叉树。 
B.树中一定没有度为 1 的结点。 
C.树中两个权值最小的结点一定是兄弟结点。 
D.树中任一非叶结点的权值一定不小于下一层任一结点的权值。 

参考答案:A
答案解析:考查哈弗曼树的特性。 
哈夫曼树为带权路径长度最小的二叉树,不一定是完全二叉树。哈夫曼树中没有度为1的结点,B 正确;构造哈夫曼树时,最先选取两个权值最小的结点作为左右子树构造一棵新的二叉树,C 正确;哈夫曼树中任一非叶结点 P 的权值为其左右子树根结点权值之和,其权值不小于其左右子树根结点的权值,在与结点 P 的左右子树根结点处于同一层的结点中,若存在权值大于结点 P 权值的结点 Q,那么结点 Q的兄弟结点中权值较小的一个应该与结点 P 作为左右子树构造新的二叉树,综上可知,哈夫曼树中任一非叶结点的权值一定不小于下一层任一结点的权值。 


登录后发布评论

暂无评论,来抢沙发