复习——哈夫曼树及哈夫曼编码
1.哈夫曼树的构造
给定N个权值为{w1,w2,w3,…,wN}的结点（比如可以根据一个字符串中字母出现的频率计算权值）。构造哈夫曼树的算法流程如下：
1.将这N个结点分别作为N棵仅含一个结点的二叉树，构成森林F；
2.构造一个新结点，并从F中选取两棵根结点权值最小的树作为新结点的左、右子树（左边的权<右边的权），并将新结点的权值置为左、右子树上根结点的权值之和；
3.从F中删除刚才选取的两棵树，同时将新生成的树放入F；
4.重复步骤2和3，直到F中只剩下一棵树为止。
2.哈夫曼编码
首先先了解前缀编码这个概念：如果没有一个编码是另一个编码的前缀，则称这样的编码为前缀编码。如0、101和100就是前缀编码，对于前缀编码的解码很简单，如00101100可唯一地被解码成0、0、101、100.
哈夫曼编码是前缀编码。
构造哈夫曼编码首先要构造出一棵哈夫曼树。首先将每个出现的字符当作一个独立的结点，其权值为它出现的频度，然后构造出对应的哈夫曼树。显然，所有的字符结点都是叶子结点。
看一个例子：
树中所有叶子结点的带权路径长度（WPL）定义如下：
WPL = ∑ 叶子结点的权值 × 结点到根结点的分支个数
因此，上面这棵哈夫曼树的WPL为：
WPL=145+3(12+13+16)+4*(5+9)=224
总结一下：利用哈夫曼树可以设计出总长度最短的二进制前缀编码！