数据结构——树——哈夫曼树

秒速五厘米 2022-04-16 00:42 314阅读 0赞

![在这里插入图片描述][20181114213744968.PNG]  
![在这里插入图片描述][201811142141429.PNG]  
下列叙述错误的是（B）。  
A.一棵哈夫曼树的带权路径长度等于其中所有分支结点的权值之和  
B.当一棵具有n 个叶子结点的二叉树的WPL 值为最小时，称其树为哈夫曼 树，其二叉树的形状是唯一的  
C.哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近  
D.哈夫曼树的结点个数不能是偶数

对N（N≥2）个权值均不相同的字符构造哈夫曼树。下列关于该哈夫曼树的叙述中，错误的是： D  
A. 树中一定没有度为1的结点  
B.树中两个权值最小的结点一定是兄弟结点  
C. 树中任一非叶结点的权值一定不小于下一层任一结点的权值  
D. 该树一定是一棵完全二叉树

## 哈夫曼树的构造 ##

![在这里插入图片描述][2018111421395185.PNG]

## 哈夫曼编码 ##

为了避免二义性，使用前缀码：  
前缀码prefix code：任何字符的编码都不是另一字符编码的前缀 可以无二义地解码  
![在这里插入图片描述][20181114214829878.PNG]![在这里插入图片描述][20181114214921694.PNG]若以｛4，5，6，3，8｝作为叶子节点的权值构造哈夫曼树，则带权路径长度是（D）。  
A.28  
B.68  
C.55  
D.59

设一段文本中包含字符\{a, b, c, d, e\}，其出现频率相应为\{3, 2, 5, 1, 1\}。则经过哈夫曼编码后，文本所占字节数为：C  
A.40  
B.36  
C.25  
D.12

设一段文本中包含4个对象\{a,b,c,d\}，其出现次数相应为\{4,2,5,1\}，则该段文本的哈夫曼编码比采用等长方式的编码节省了多少位数？ B  
A.0  
B.2  
C.4  
D.5

由分别带权为9、2、5、7的四个叶子结点构成一棵哈夫曼树，该树的带权路径长度为： C  
A.23  
B.37  
C.44  
D.46

已知字符集\{ a, b, c, d, e, f, g, h \}。若各字符的哈夫曼编码依次是 0100, 10, 0000, 0101, 001, 011, 11, 0001，则编码序列 0100011001001011110101 的译码结果是：D  
A.acgabfh  
B.adbagbb  
C.afbeagd  
D.afeefgd

[哈夫曼树的应用][Link 1]

[20181114213744968.PNG]: /images/20220416/3c9ccacea83a4bc2b1198e05fc323682.png
[201811142141429.PNG]: /images/20220416/790de01483b8486e8a15cbe9d6700047.png
[2018111421395185.PNG]: /images/20220416/87251438dcd846b9983fb8c5d08251ee.png
[20181114214829878.PNG]: https://img-blog.csdnimg.cn/20181114214829878.PNG
[20181114214921694.PNG]: /images/20220416/ef14c8950b834789a799b146797539dc.png
[Link 1]: https://blog.csdn.net/qq_42623428/article/details/82902074