哈夫曼树的定义

例如：

哈夫曼树就是要构造一棵WPL最小的二叉树。

哈夫曼树的构造

哈夫曼树构造时，每次把权值最小的两颗二叉树合并。
首先把权值按照由小到大排序：
1，2，3，4，5
其中最小的权值为1，2，因此将1，2合并，合并生成的新的节点的权值为二者的和：

然后再选择权值最小的两颗二叉树合并（3，3），得到：

然后在选择最小的权值4，5合并，得到

最后，将6和9合并，即可构造哈夫曼树

用程序实现时，其中的关键问题就是如何选取最小的两个权值：

• 第一种方式：先排序，然后再选择较小的两个合并
• 第二种方式：先建立堆，然后选择较小的两个合并
• 第二种方式效率要高，第一种方式，每次合并后，然后将合并的权值插入到原来排好序的节点中，因为原权值是排好序的，将合并的权值选择合适的位置插入即可（插入，找到合适的位置O(n)或O(log2(n))，插入后需要移动后面的节点）。而第二种方式，直接通过将合并后的权值加入到堆的末尾，然后执行向下过滤即可（时间复杂度为O(logn)）。第二种方式较第一种方式避免了移动后面节点的过程。

哈夫曼树的特点

• 没有度为1的结点（因为每次都是两个结点合并在一起）

• n个叶子结点的哈夫曼树共有2n-1个结点（二叉树中有下面这个结论，由这个结论可以推出）
  

• 哈夫曼树的任意非叶节点的左右子树交换后仍是哈夫曼树（构造哈夫曼树的时候，左、右子树的顺序没有影响）

• 对同一组权值{w1,w2, …… , wn}，可能会存在不同构的两棵哈夫曼树
  

对于二叉树的同构：给定两棵树T1和T2。如果T1可以通过若干次左右孩子互换就变成T2，则我们称两棵树是“同构”的，如下图两棵二叉树就是同构的。

哈夫曼编码

给定一段字符串，如何对字符进行编码，可以使得该字符串的编码存储空间最少？

假设有一段文本，包含58个字符，并由以下7个字符构：a，e，i，s，t，空格（sp），换行（nl）；这7个字符出现的次数不同。如何对
这7个字符进行编码，使得总编码空间最少？
（1）用等长ASCII编码：58 ×8 = 464位；
（2）用等长3位编码：58 ×3 = 174位；
（3）不等长编码：出现频率高的字符用的编码短些，出现频率低的字符则可以编码长些？

在进行不等长编码的时候，要注意避免二义性。例如编码方式为：a:1，e:0，s:10，t:11，那对于10的解码，即可以解码为ae，也可以解码为s，产生了二义性。

只要编码满足前缀码的条件，就可以避免二义性问题，所谓前缀码：任何字符的编码都不是另一个字符编码的前缀。此时便可以进行无二义的解码。

实现过程，如何保证编码无二义性，当用二叉树表示编码时，当所有要编码的结点都在二叉树的的叶结点的时候，就不会出现一个结点的编码是另一个结点编码的前缀。

具体编码举例：
例如：四个字符的频率: a:4, u:1, x:2, z:1，用二叉树进行编码，字符只在叶节点，左右分支编号分别为0，1

此时的代价为：

如何构造一棵编码代价最小的二叉树呢？这时候可以发现构造一棵哈夫曼树就可以保证编辑代价最小。

例：