哈夫曼树和哈夫曼编码（文件压缩）

哈夫曼树（Huffman Tree)
带权路径长度（WPL）:设二叉树有n个叶子结点，每个叶子结点带有权值Wk,从根节点到每个叶子结点的长度为Lk,则每个叶子结点带权路径长度之和就是(wk* Lk)求和
最优二叉树或哈夫曼树：WPL最小的二叉树

哈夫曼树的构造：每次把权值最小的两棵二叉树合并

 1 HuffmanTree Huffman(MinHeap H)
 2 {
 3     //这里最小堆的元素类型为HuffmanTree，排序的原则是结点的权值数据
 4     //假设H->Size个权值已经存在在H->Data[]->weight里
 5     int i, N;
 6     HuffmanTree T;
 7 
 8     BuildMinHeap(H);        //根据结点的权值将H调整为最小堆
 9     N = H->Size;
10     for (i = 1; i < N; i++)        //做H->Size - 1次合并
11     {
12         T = (HuffmanTree)malloc(sizeof(struct HTNode));        //创建一个新的哈夫曼结点
13         T->Left = DeleteMin(H);        //将最小堆中的最小元素，即根节点删除后返回，作为这个哈夫曼结点的左子结点
14         T->Right = DeleteMin(H);        //再次将最小堆中的根节点删除后返回，作为这个哈夫曼树的右子结点
15         //哈夫曼节点的权值等于左右子节点的权值之和
16         T->weight = T->Left->weight + T->Right->weight;
17         Insert(H, T);
18     }
19 
20     return DeleteMin(H);    //最小堆中最后一个元素即使指向哈夫曼树根节点的指针
21 }

哈夫曼树的特点：
没有度为1的结点
n个叶子结点的哈夫曼树共有2n-1个结点
哈夫曼树的任意非叶结点的左右子树交换后仍是哈夫曼树
对同一组权值，存在不同构的两棵哈夫曼树，但两棵树的WPL相等

哈夫曼编码（文件压缩）：
给定一段字符串，如何对字符进行编码，可以使得该字符串的编码存储空间最少

前缀码：（prefix code)任何字符的编码都不是另一字符编码的前缀，可避免二义性
二叉树表示法：每个字符通过从根节点开始用0指示左分支，用1指示右分支而已记录路径的方法表示出来
用二叉树进行编码：
（1）左右分支：0、 1
（2）字符只在叶结点上
用哈夫曼树的规则构造这棵二叉树

哈夫曼编码对应的解压过程：

依次读入文件的二进制码，从哈夫曼树的根节点出发，若当前读入0，则走向左孩子，否则走向右孩子。

一旦到达某一叶子时便译出相应的字符。然后重新从根出发继续下一个字符的译码，直至文件结束