哈夫曼树

基本概念

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

 

概念1：什么是路径？

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

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

 

概念2：什么是路径长度？

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

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

 

概念3：什么是结点的带权路径长度？

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

结点的带权路径长度，是指树的根结点到该结点的路径长度，和该结点权重的乘积。

假设结点H的权重是3，从根结点到结点H的路径长度也是3，因此结点H的带权路径长度是 3 X 3 = 9。

 

概念4：什么是树的带权路径长度？

在一棵树中，所有叶子结点的带权路径长度之和，被称为树的带权路径长度，也被简称为WPL。

仍然以这颗二叉树为例，树的路径长度是 3X3 + 6X3 + 1X2 + 4X2 + 8X2 = 53。

 

哈夫曼树是由麻省理工学院的哈夫曼博士于1952年发明，这到底是一颗什么样的树呢？

刚才我们学习了树的带权路径长度（WPL），而哈夫曼树（Huffman Tree）是在叶子结点和权重确定的情况下，带权路径长度最小的二叉树，也被称为最优二叉树。

 

举个例子，给定权重分别为1，3，4，6，8的叶子结点，我们应当构建怎样的二叉树，才能保证其带权路径长度最小？

原则上，我们应该让权重小的叶子结点远离树根，权重大的叶子结点靠近树根。

下图左侧的这棵树就是一颗哈夫曼树，它的WPL是48，小于之前例子当中的53：

需要注意的是，同样叶子结点所构成的哈夫曼树可能不止一颗，下面这几棵树都是哈夫曼树：

 

假设有6个叶子结点，权重依次是2，3，7，9，18，25，如何构建一颗哈夫曼树，也就是带权路径长度最小的树呢？

第一步：构建森林

我们把每一个叶子结点，都当做树一颗独立的树（只有根结点的树），这样就形成了一个森林：

在上图当中，右侧是叶子结点的森林，左侧是一个辅助队列，按照权值从小到大存储了所有叶子结点。至于辅助队列的作用，我们后续将会看到。

第二步：选择当前权值最小的两个结点，生成新的父结点

借助辅助队列，我们可以找到权值最小的结点2和3，并根据这两个结点生成一个新的父结点，父节点的权值是这两个结点权值之和：

第三步：从队列中移除上一步选择的两个最小结点，把新的父节点加入队列

也就是从队列中删除2和3，插入5，并且仍然保持队列的升序：

第四步：选择当前权值最小的两个结点，生成新的父结点。

这是对第二步的重复操作。当前队列中权值最小的结点是5和7，生成新的父结点权值是5+7=...

课后习题

 

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