哈夫曼树（最优二叉树）的概念以及构造

哈夫曼树产生的背景

在实际生活和生产应用中，我们往往会遇到综合比较一系列的离散量的问题；比如说车站根据包裹的重量以及旅途的长短来确定携带行李的价格，或者我们根据一定的重量范围来给一箱铁球进行分类。这一类问题的解决思路是： 1、 根据实际需要划分出分类的标准； 2、 按一定的顺序（算法）将实际的数据归到相应的类别里。 一般情况下，我们所确定的分类标准并不能保证每一类的数据量是平均分配的；也就是说，由于每一类数据出现的概率不同，造成当采用不同的算法时所需的运算次数的不同。当然，在实际生产生活中，我们更希望得到一种最快，最简洁同时也不会产生歧义的算法。在这个背景下，哈夫曼树以及哈夫曼算法应运而生。

准备概念

森林：森林由n(n>=2)个二叉树组成，它的遍历可以归结为二叉树的遍历，即以其中一棵二叉树的根结点为森林的“根结点”，之后每一个二叉树的根结点都依次相连，由此组成了一个大的二叉树——森林向二叉树的转化。 路径和路径的长度：从树中的一个结点到另一个结点之间的分支构成这两个结点之间的路径，路径上的分支数目称作路径长度。 对于一个二叉树，其在第n层上的结点到根结点的路径长度为n-1。 结点的权：根据应用的需要给树的结点赋的权值。 结点的带权路径长度：从根结点到该结点的路径长度与该几点权的乘积。 树的带权路径长度（WPL）：树中所有叶子的带权路径长度之和。

哈夫曼二叉树及其构造

有了以上的概念，哈夫曼二叉树的定义就变得水到渠成。所谓哈夫曼二叉树（最优二叉树），就是带权路径长度最小的二叉树（注意这里的带权路径）。 因为树的带权路径长度只与所有叶子的带权路径长度有关，所以对于一个哈夫曼树，其真正其作用的数据是存在于叶子上。 再回到问题产生的根源。我们说在现实的分类中，每一类数据出现的概率不尽相同；这些数据出现的概率可以被看做哈夫曼树中叶子的权值。为了获取最短的路径，也就是带权路径长度最短的二叉树，我们希望那些权值低的数据拥有相对较长的对根结点的路径长度。根据这一思路，我们可以从一群离散的数据中构造出一颗哈夫曼树，具体的算法如下：

1. 根据给定的n个权值{w1 ,w2 ,...,wn }构造n棵二叉树的集合F={T1 ,T2 ,...,Tn }，其中每棵二叉树Ti中只有一个带权为wi的根结点，其左右子树均空。
2. 在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根 结点的权值为其左、右子树上根结点的权值之 和。
3. 在F中删除这两棵树，同时将新得到的二叉树加入F中。
4. 重复2和3，直到F中只含一棵树为止。这棵树便是最优二叉树。

例如，有权值分别为 5、10、15、20、25、40的结点，根据以上算法构造出一个哈夫曼树。

1. 取这六个树中最小的两个树5、10连成一个二叉树，其权值为15；此时森林里的树变为15（5、10）、15、20、25、40。
2. 取这五个树中最小的两个树（15（5、10）、15），构成一个新的二叉树30（（5、10）、15）；此时森立里的树变为20、25、30（（5、10）、15）、40。
3. 继续上述过程，得到一个新的二叉树45（20、25）；此时的森林变为30（（5、10）、15）、40、45（20、25）。
4. 继续得到二叉树70（（5、10）、15）、40）；则森林里只剩下两棵树：70（（5、10）、15）、40）与45（20、25）。
5. 最后将这两棵二叉树合并成为一棵二叉树115（（（5、10）、15）、40）、（20、25）），完成了哈夫曼树的构造。
6. 计算WPL=(5+10)4+153+402+(20+25)2=275。

以上便是哈夫曼树（最优二叉树）的相关概念和构造方法。根据最后二叉树可以解决类似于文章开头提到的一些实际问题。同时还另外引申出了哈夫曼编码——即不等长编码，实现数据总长度的最优化。