讲解（上）在线视频

本节，我们来学习哈夫曼树

先来看一个概念，树的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，表示之前没有选过