【IT168 文档】认识哈夫曼树之前首先我们简单的来了解一下二叉树，不难理解，二叉树就是每个节点都只有2个子节点的树状结构，也就分为父节点(parent node)、左子树(left child)和右子树(right child)。每个节点最多只能有2个节点，当然也可以更少，比如只有左节点没有右节点或者相反，没有子节点的节点我们称之为叶节点，有子树的称之为根节点。
二叉树相关就先介绍到这里，我们还是回到主题。首先，哈夫曼树就是一种特殊的二叉树，也是一种加权二叉树。首先，我们对我们需要储存到二叉树的数据赋予权重，权比较高的放在浅层，权重低的放在深层，并且所有的数据都储存在叶节点。接下来的问题就是如何构造这个哈夫曼树了。
举个例子：我们要储存的数据及其权重分别为：a:1|b:4|c:4|d:2|e:7|f:3，下面将通过例子来讲解哈夫曼树的构造方法
首先，将数据按权重排序
1 | 2 | 3 | 4 | 4 | 7
我们先将权最低的2个节点组成一个二叉树，根节点为A，没有数据，但权重为2个子节点的和，并将他们的根节点放入列表重新排序：
引用
/ \
a(1) b(2)
重复上一步骤，取新的根节点为B
引用
/ \
A(3) f(3)
/ \
a(1) b(2)
引用
/ \ / \
A(3) f(3) d(4) c(4)
/ \
a(1) b(2)
引用
/ \
B(6) C(8)
/ \ / \
A(3) f(3) d(4) c(4)
/ \
a(1) b(2)
引用
/ \
e(7) D(14)
/ \
B(6) C(8)
/ \ / \
A(3) f(3) d(4) c(4)
/ \
a(1) b(2)
这个哈夫曼树我们就算完成了，最后将无关的东西去掉：
引用
/ \
e ○
/ \
○ ○
/ \ / \
○ f d c
/ \
a b
大功告成!
哈夫曼树的意义就在于可以对其中的数据重新编码，编码方式很简单，左树为0右树为1，每下一层加一个数字，以上图中的例子来说，abcdef对应编码就是：
|b|1001
|c|111
|d|110
|e|0
|f|101
大家不难发现，这几个编码没有任何一个是另一个编码的前置。这是由哈夫曼树的特性决定的，哈夫曼树所有的数据都在页节点，如果出现一个数据是另一个数据编码的前置，这个数据必然在另一个数据的路径前，也就是在根节点，然而这是不可能的，这也确保了解码的唯一性，避免了歧义的出现，就拿刚才的例子来说，11111001011001的解码只可能是cdefb而不会是别的。
