主要内容 #
- 哈夫曼树知识点回顾
- 哈夫曼树的构建过程
- 哈夫曼树练习题
1. 哈夫曼树知识点回顾 #
路径:在一棵树中,一个结点到另一个结点之间的通路,称为路径。图 1 中,从根结点到结点 a 之间的通路就是一条路径。
路径长度:在一条路径中,每经过一个结点,路径长度都要加 1 。例如在一棵树中,规定根结点所在层数为1层,那么从根结点到第 i 层结点的路径长度为 i – 1 。下图中从根结点到结点 c 的路径长度为 3。
结点的权:给每一个结点赋予一个新的数值,被称为这个结点的权。例如,下图中结点 a 的权为 7,结点 b 的权为 5。
结点的带权路径长度:指的是从根结点到该结点之间的路径长度与该结点的权的乘积。例如,下图中结点 b 的带权路径长度为 2 * 5 = 10 。
树的带权路径长度为树中所有叶子结点的带权路径长度之和。通常记作 “WPL” 。例如下图所示的这颗树的带权路径长度为:
WPL = 7 * 1 + 5 * 2 + 2 * 3 + 4 * 3
当用 n 个结点(都做叶子结点且都有各自的权值)试图构建一棵树时,如果构建的这棵树的带权路径长度最小,称这棵树为“最优二叉树”,有时也叫“赫夫曼树”或者“哈夫曼树”。
在构建哈夫曼树时,要使树的带权路径长度最小,只需要遵循一个原则,那就是:权重越大的结点离树根越近。在图 1 中,因为结点 a 的权值最大,所以理应直接作为根结点的孩子结点。
2. 哈夫曼树的构建过程 #
对于给定的有各自权值的 n 个结点,构建哈夫曼树有一个行之有效的办法:
- 在 n 个权值中选出两个最小的权值,对应的两个结点组成一个新的二叉树,且新二叉树的根结点的权值为左右孩子权值的和;
- 在原有的 n 个权值中删除那两个最小的权值,同时将新的权值加入到 n–2 个权值的行列中,以此类推;
- 重复 1 和 2 ,直到所以的结点构建成了一棵二叉树为止,这棵树就是哈夫曼树。
下图中,(A)给定了四个结点a,b,c,d,权值分别为7,5,2,4;第一步如(B)所示,找出现有权值中最小的两个,2 和 4 ,相应的结点 c 和 d 构建一个新的二叉树,树根的权值为 2 + 4 = 6,同时将原有权值中的 2 和 4 删掉,将新的权值 6 加入;进入(C),重复之前的步骤。直到(D)中,所有的结点构建成了一个全新的二叉树,这就是哈夫曼树。
3. 哈夫曼树练习题 #
1.用5个权值{3, 2, 4, 5, 1}构造的哈夫曼(Huffman)树的带权路径长度是( )
解析:33;先构造哈夫曼树,得到各叶子的路径长度之后便可求出WPL。
2. 具有10个叶子结点的哈夫曼树,最大高度为( ),最小高度为( )。
解析:10,5; n个叶子结点的哈夫曼树,最大高度为n,(除最上一层和最下一层每层一个叶子点),最小高度为log2 n +1。
3. 根据使用频率为5的字符设计的哈夫曼编码不可能是( )
A.111,110,10,01,00
B、000,001,010,011,1
C.100,11,10,1,0
D、001,000,01,11,10
解析:选C;C中,100和10冲突(单独存在1、0和其它的也冲突),即一个结点既是叶子结点又是内部结点,哈夫曼树中不可能出现这种情况。 一个树可以看做由三种结点组成:根结点(唯一)、内部结点、叶结点。
4. 假设有一组字符{a,b,c,d,e,f},对应的频率分别为5%,9%,12%,13%,16%,45%。请问以下哪个选项是字
符a,b,c,d,e,f分别对应的一组哈夫曼编码?( )
A. 1111,1110,101,100,110,0
B. 1010,1001,1000,011,010,00
C. 000,001,010,011,10,11
D. 1010,1011,110,111,00,01
解析:选A。