学科分类
目录
数据结构

霍夫曼树的构造

树的带权路径长度越小其运算效率越高,但是如何构造出一棵霍夫曼树呢?根据霍夫曼提出的构造最优二叉树的算法思想,构造霍夫曼树的基本步骤如下所示:

(1)有n棵权值分别为w1、w2、w3、…、wn的二叉树,其左右子树都为空(可理解为是确定权值的结点);

(2)从中选取出权值最小的两棵树组成一棵新的树。如果有结点权值相同的,可以任选两棵,为了保证新树仍是二叉树,需要增加一个新结点作为新树的根,将所选的两棵树作为新树根的左右子树,不分先后,将两个孩子的权值之和作为新树根的权值。删除已经选中的树,使新生成的树参与下一轮选择。

(3)对新树集重复步骤(2),直到集合中剩下最后一棵二叉树,这棵二叉树便是霍夫曼树。

为了让读者更好的理解霍夫曼树的构造过程,下面我们用图示来分析这个构造过程。

(1)有一片确定权值的二叉树森林,如图1所示。

图1 确定权值的森林

(2)从中选出权值最小的两棵二叉树,为c和d,新增加一个根结点,以两个孩子的权值之和作为新的根结点的权值。如图2所示。

图2 新二叉树

将c和d结点从集合中删除,将新生成的树放入集合中。

(3)然后再从剩下的森林中找出两棵权值最小的树,权值为6与5的两个棵,组成一棵新二叉树,如图3所示。

图3 新二叉树

将选中的两棵树从集合中删除,将新生成的二叉树放入集合。

4、再从集合中选出两棵权值最小的树组成一棵新的二叉树,如图4所示。

图4 新二叉树

至此,森林中只剩下如图6-76中的这一棵二叉树,这就是一棵霍夫曼树。它的带权路径长度为7×1+4×3+2×3+5×2 = 35。

霍夫曼树的应用非常广,在不同的应用中叶子节点的权值可以作不同的解释。霍夫曼树应用于信息编码中,权值可以看成某个符号出现的频率;应用到排序过程中,权值可以看成是已排好次序,等待合并的序列长度等。

需要注意的是:初始森林中的二叉树都是孤立的结点。n个结点需要合并n-1次,新增n-1个新结点,最终求得的霍夫曼树共有2n-1个结点。霍夫曼树是严格的二叉树,没有度数为1的结点。

点击此处
隐藏目录