当前课程知识点：数据结构 > 第5章 树和二叉树 > 5.7 Huffman树 > 讲解（上）
本节，我们来学习哈夫曼树
先来看一个概念，树的WPL
也就是树的带权路径长度
我们给定n个带权值的叶结点，注意是叶结点
而且，它们都带有权值
现在，利用这n个叶结点，构造出一棵二叉树
比如这棵树，这4个给定的红色的结点，是作为叶结点出现在二叉树当中的
它们的权值分别是7、5、2、4
现在，我们来定义一个量，叫li，它是指从根结点走到叶结点i的路径长度
也就是路径中边的条数
比如，这4个叶结点
它们的li都是2
因为，从根结点走到这些叶结点
只需要经历2条边
现在，我们给出树的WPL定义
它是li
乘上该结点的权值
最后，所有的结点累加，就可以了
比如这棵树，它的WPL
就是(7+5+2+4)*2
因为，这4个叶结点出现在同一层
所以，我们就直接先相加，再乘以2
除了这样一棵树之外
我们利用相同的给定初始值
7、5、2、4
作为叶结点，还能构造出其他的二叉树
比如这棵树
4、2、5、7，同样出现在叶结点的位置
但是，它的WPL却跟刚才不一样
我们还能继续构造
7、5、2、4，依然出现在叶结点
它的WPL是35
比其他两棵树的WPL要小一些
现在，我们来看哈夫曼树的定义
哈夫曼树是指WPL最小的二叉树
它也称为最优二叉树，哈夫曼树
会广泛地应用于
哈夫曼编码、判定优化等等
我们待会会看到这样的例子
刚才我们画出的这三棵二叉树，都是用7、5、2、4作为叶结点
是否还有其他WPL
更小的二叉树呢
换句话说
我们怎么样去构造哈夫曼树呢
保证WPL是最小的呢
现在，我们介绍哈夫曼树的构造方法
初始条件
给定了n个权值，w1
一直到wn
比如刚才的
7、5、2、4
n个叶结点的权值
现在，我们令一个集合F
等与若干棵树构成的集合
每一棵树是什么呢
在初始情况下
它仅有一个结点
这个结点就是我们给定的叶结点
比如7、5、2、4
各自作为一棵包含唯一结点的树
现在，F就包含给定的n个结点构成的n棵树
紧接着，我们重复以下的步骤
n-1次，开始做循环
我们从F当中，选取两棵根结点权值最小的树
比如，第1次选
肯定是选这里的2和4
因为，它们的根结点权值最小
然后，把这两棵树组成一棵新树
新树的根，它的权值是左、右子树的根结点权值之和
也就是，这棵树的根结点
权值是6
然后
把选出来的两棵树，从F当中删掉
并且，把新创建的这棵树，加到F里面
实际上
我刚才画的时候，已经完成了这个过程
把2和4这两棵树删掉
然后，把新生成的这棵以6为根结点的树，加到F里面
大家看到
每执行这样一次循环，F里面的树的个数是少了一个的
所以，我们一共执行n-1次
之后
F里面就剩下唯一的一棵树了
这棵树就是最终我们要求解的
哈夫曼树
现在，我们通过一批具体的数据，来看看如何来构造哈夫曼树
比如，这里给出来5个叶结点的权值
为了方便，我把它们排好序了
2、3、4、5、7
构造出来的哈夫曼树是这样的
我们看它是如何构造出来的
按照刚才讲的算法
首先，选两个权值最小的2、3
也就是这棵树，组成的这棵树
我们把它加到这个集合里面
并且，把选出来的这两棵树删掉
下一个，再选两个根结点
权值最小的，最小的是4，下一个次小的
应该是5
这时候，你会发现有两个5，两个5我们到底选哪一个呢
我们先选这个
也就是，以两个叶结点4、5
组成新的一棵树
现在，新树的根结点权值是9
注意，我们选的是这个5
把这两棵树删掉
然后，再重复刚才的过程
现在，根结点权值最小的是7和5
那么，它们再组成一棵新的树
那就是这棵树
组成12
然后，把这棵树和7删掉
最后，只有两棵树了
让它们组成一棵最终的树
这个就是最后的解
我们怎么保证这样一种算法
它创建出来的哈夫曼树的WPL是最小的呢
我们分析一下WPL的构成
它是wi乘上li，wi已经给定了
没法改
要保证这二者的乘积比较小
我们只能让那些wi比较大的
它的li要小一些
也就是说，让权值大的
后选
因为后选
它将来离根会比较近
而权值小的
我们可以让它的li大一点，也就是先选
比如，这里的2和3
先选出来
将来，它们离根是比较远的
也就是li比较大
这样，从整体上保证各个结点的
wi乘上li的值较小
我们从这个角度，能分析出刚才所采用的算法
它的本质
另外，还有一点需要注意的是
哈夫曼树可能不唯一
刚才，我们构造出第一棵树的时候
第二次再选的时候
发现有两个5
我们刚才选的是这个5
我们完全可以去选
这个5，也就是这棵哈夫曼树
大家看到，在第二次选的时候
我们选的4和5，选的是这个5
而不是刚才叶结点的这个5
它的WPL也是最小的
通过计算
你会发现，这两棵哈夫曼树，它们的WPL
同为47，都是最小的
所以，对于某些给定的数据
哈夫曼树可能不唯一
但是WPL同为最小
另外
需要注意，哈夫曼树当中，没有度为1的结点
这是因为，我们每次都是选两棵树
构成一棵新的树
所以
没有度为1的结点
最后，n个叶结点的哈夫曼树，共有2*n-1个结点
这个很容易证明，我们前面讲过，二叉树有一个性质
n0=n2+1
现在，n0就是叶结点，叶结点有n个，那么，度为2的结点个数就等于n-1
由于哈夫曼树当中，没有度为1的结点
所以，总的结点个数就是n0+n2，也就是2*n-1
现在，我们来看看哈夫曼树的构造算法
具体的实现
首先
我们把哈夫曼树，它的结构体定义给出来
我们定义的结构体比较简单
是采用顺序方式存储的
每一个结点，我们存放以下的4部分信息，分别是结点的权值(假设就是int型)
然后是
该结点的左、右孩子
在一维数组当中的下标
同时，我们还存放了该结点的父结点
在一维数组当中的下标
可见，这时候我们采用的是顺序存储
带有孩子和父结点的下标
我们给这样一个结构体
起两个别名
第一个就是结点类型
第二个是指向结点的指针
将来，我们用第一个别名
声明一个数组
它就是由若干个结点构成的一个顺序表
也可以用第二个别名
来定义一个指向结点的指针
实际上，就是数组(顺序表)的首地址
这是刚才给出的若干个叶结点的权值，构造出来的哈夫曼树假设是这个，现在，我们来看看算法的执行过程
这里每一个横向的、包含4个格子的，就是前面这个结构体
然后，我们又定义了一个由结构体组成的数组
这个数组的长度是9
为什么是9呢
实际上
我们定义了长度为10的数组
因为，我们约定了0下标不用
实际上只用了9个这样的结点
那为什么是9呢
刚才，我们已经说过了
叶结点有n个，最后总的结点个数是2*n-1
5个叶结点
整棵树包含9个结点
现在，我们先来看初始化
把给定的前n个叶结点权值，放到前n个下标的weight成员里面去
然后，后面的
n-1个结点
它们的weight都是0，所有结点的左、右
孩子下标和父结点下标，都初始化成0
现在，我们开始做循环，第1次，我们选的是2和3这两个结点
那么，它们的下标是1和2，放到下标为6的位置，组成一棵新的树
所以，下标为6的结点
它的左、右孩子(下标)分别是1和2
同时
新树的根结点权值，应该是2、3之和
也就是5，别忘了修改对应的孩子结点
它们的父结点下标
因为2、3这两个结点
它们现在的父结点，是下标为6的
这个结点，把它们修改成6，重复刚才的过程
下面选的是4、5这两个叶子
它们的下标
是3和4
所以
再下一个创建的结点的左、右
孩子下标是3和4，根结点的权值
应该是4、5相加，9，同样，修改这两个结点的parent
把它们改成新建的这个结点
7
重复刚才的过程
我们下一次选的是5和7
5应该是
这个结点，它的权值是5
7，下标是5
我们约定，比较小的那个结点，我们放在左边，比较大的放在右边
实际上也无所谓
反过来也可以
所以，我们下一次创建的结点
它的左、右孩子下标，分别是6和5
也就是这里的5和7，权值
应该是5加7，12，对应着下标为5、6的这两个结点
它们的父结点下标，应该是8
最后
只包含两棵树没有选
也就是下标为7和8的，最后一个结点的左、右
孩子(下标)是7、8
根结点
权值应该是9加12
21
同时，下标为7、8的结点的父结点，修改成9
这样，我们就构造出了最终的哈夫曼树，在选结点的过程当中
比如我们第2次选
这里的2、3已经选过了，第二次选的时候
怎么防止2和3又被选出来呢
毕竟人选的时候
发现这地方是两个红色的
不能选了
那计算机来选的时候，很简单
因为，我们只需要判断，那些parent不为0的
是之前已经被选过了
我们已经给它们设置了父结点
所以，在选的过程当中
要保证权值是最小的两个结点
并且，它们的parent必须是0，表示之前没有选过
-讲解
-作业
-讨论1
-讨论2
-1.1 数据结构是什么
--讲解
--作业
-1.2 概念和术语
--讲解
--作业1
--作业2
-1.3 抽象数据类型
--讲解（上）
--讲解（下）
--作业
-1.4 算法及其设计要求
--讲解
--作业
-1.5 算法分析与度量
--讲解（上）
--讲解（下）
--作业1
--作业2
--讨论
-2.1 概念及ADT
--讲解
--作业
-2.2 线性表的顺序实现——顺序表
--讲解（上）
--讲解（中）
--讲解（下）
--作业1
--作业2
-2.3 线性表的链式实现——链表
--讲解（上）
--讲解（中）
--讲解（下）
--作业1
--作业2
-2.4 线性表的应用——多项式
--讲解
--作业
-讨论
-3.1 栈的定义及ADT
--讲解
--作业
-3.2 栈的顺序实现——顺序栈
--讲解
--作业
-3.3 栈的应用
--讲解
--作业
-3.4 栈与递归
--讲解（上）
--讲解（下）
--作业
-3.5 队列的定义及ADT
--讲解
--作业
-3.6 队列的顺序实现——循环队列
--讲解（上）
--讲解（下）
--作业
-讨论
-4.1 数组的定义
--讲解
--作业
-4.2 数组的顺序实现
--讲解
--作业1
--作业2
-4.3 特殊矩阵的压缩存储
--讲解
--作业
-4.4 稀疏矩阵的压缩存储
--讲解（上）
--讲解（下）
--作业
-讨论
-5.1 概念及术语
--讲解
--作业
-5.2 二叉树及其性质
--讲解
--作业1
--作业2
-5.3 二叉树的存储
--讲解
--作业
-5.4 二叉树的遍历及创建
--讲解（上）
--讲解（下）
--作业
-5.5 线索二叉树
--讲解
--作业
-5.6 树与森林
--讲解
--作业
-5.7 Huffman树
--讲解（上）
--讲解（下）
--作业
-讨论
-6.1 概念和术语
--讲解
--作业
-6.2 存储与实现
--讲解（上）
--讲解（下）
--作业
-6.3 遍历
--讲解（上）
--讲解（下）
--作业
-6.4 最小生成树
--讲解（上）
--讲解（下）
--作业1
--作业2
-6.5 拓扑排序
--讲解
--作业
-6.6 最短路径
--讲解
--作业
-讨论
-7.1 概念和术语
--讲解
--作业
-7.2 静态查找表
--讲解（上）
--讲解（下）
--作业
-7.3 二叉排序树
--讲解（上）
--讲解（下）
--作业
-7.4 平衡二叉树
--讲解
--作业
-7.5 哈希表
--讲解（上）
--讲解（下）
--作业
-讨论
-8.1 概念
--讲解
--作业
-8.2 插入排序
--讲解（上）
--讲解（下）
--作业
-8.3 交换排序
--讲解（上）
--讲解（下）
--作业
-8.4 选择排序
--讲解（上）
--讲解（中）
--讲解（下）
--作业
-8.5 归并排序
--讲解
--作业
-讨论
