什么是哈夫曼树

今天看到一道题，是这样描述的：

设给定一个权值集合W=(3，5，7，9，11)，要求根据给定的权值集合构造一棵哈夫曼树并计算哈夫曼树的带权路径长度WPL？

就以这道题为基准，让我们来看看哈夫曼树是怎么一回事。

首先，哈夫曼树是一个叫做哈夫曼博士发明的，可以利用结点权重和路径长度，通过树的带权路径长度(WPL)，来求出最优二叉树。

1. 树的路径

如上图中的树所示，结点A到结点E的路径为A, B, E。

2. 路径长度

如上图中的树所示，结点A到结点D之间有两条边，所以AD的路径长度为2。

3. 结点的带权路径长度

如上图中的树所示，假设结点D的权重是3，从根结点到D的路径长度是2，所以结点D的带权路径长度3*2=6。

4. 树的带权路径长度WPL

如上图中的树所示，假设结点C的权重是2，结点D的权重是3，结点E的权重是5；我们再看路径长度，结点C的路径长度为1，结点D和结点D的路径长度都为2，所以树的带权路径长度WPL = 1*2 + 2*3 + 2*5 = 18。

5. 构建哈夫曼树（最优二叉树）

所谓最优二叉树就是带权路径长度最小的树，所以不是随便构建一棵树都是哈夫曼树，根据上面的WPL求值方法，我们可以推断：在构建二叉树的时候，只需要把结点权重小的往根结点上靠，这样的树计算出来的WPL往往是最小的，这棵树也就是哈夫曼树。

5.1 借助队列，构建深林

接下来回到上面的题目来，题目给出了对应的权值集合(3, 5, 7, 9, 11)，我们先构建深林（把每一个结点当做一颗独立的树），借助队列来构建对应的树

5.2 取两个结点，生成子树

左侧借助队列的形式从小到大存储对应权重的结点，按权重由小到大的顺序排列，取权重最小的结点2, 3，以权重的和5为父结点生成一棵树。

5.3 从队列中删除选中的结点，插入新的结点

把上一步中选中的两个结点从队列中删除，并插入上面新生成的父结点，新的队列按从小到大排序，然后重5.2的操作。

5.4 当新插入的结点不在队列第一个元素的下面，应生成一个新的子树

接下来挑选7, 8，生成新的父结点15，放入队列中排序后处于最下面的位置，而此时选择两个结点并没有选中新生成的结点15，而是选中9和11，遇到这种情况时，我们应该考虑在原有树的外部，重新生成一颗新的子树，然后重复5.2的步骤，再把两颗子树通过生成父结点，然后可以根据树的带权路径长度算法算出WPL的值（WPL=78）

其实哈夫曼树在生活中有广泛的应用，比如通信领域的哈夫曼编码，计算机程序中的哈夫曼编码等等。