哈夫曼树和哈夫曼编码

叶结点带权路径长度最小的二叉树
构造
给定n个权值分别为w1, w2, ...wn的结点，构造哈夫曼树

1. 将这n个结点分别作为n棵仅含一个结点的二叉树，构成森林F
2. 构造一个新结点，从F中选取两棵根节点权值最小的树，作为新结点的左右子树，并将新结点的权值置为左右子树上根结点的权值和
3. 从F中删除刚才选出的两棵树，同时将新的到的树加入F
4. 重复23直到F中只剩一棵树
   构造过程中，需经过n-1次合并，每次合并会新建一个节点，共新建了n-1个结点，结点总数为2n-1

用最小堆来构造一个哈夫曼树

typedef struct TreeNode *HuffmanTree;
srtuct TreeNode
{
    int Weight;
    HuffmanTree Left, Right;
}
HuffmanTree Huffman(MinHeap H)
{
    int i;
    HuffmanTree T;
    BuildMinHeap(H);  //按权值调整为最小堆
    for(i=1;i<H->Size;++i){
        T=malloc(sizeof(struct TreeNode));
        T->Left=DeleteMin(H);
        T->Right=DeleteMin(H);
        T->Weight=T->Left->Weight+T->Right->Weight;
        Insert(H, T);
    }
    T=DeleteMin(H);
    return T;
}

哈夫曼编码
是一种可变长度编码，对频率高的字符赋予短编码，频率低的字符长编码
前缀编码：没有一个编码是另一个编码的前缀