哈夫曼树

带权路径长度(WPL):设二叉树有n个叶子结点，每个叶子结点带有权值wk，从根结点到每个叶子结点的长度为lk，则每个叶子结点的带权路径长度之和就是每个的路径和权重相乘之和。

最优化二叉树或哈夫曼树：wpl最小二叉树。

哈夫曼树的构造

每次把权值最小的两棵二叉树合并。

typedef struct TreeNode *HuffmanTree;
struct TreeNode{
    int Weight;
    HuffmanTree Left,Right;
}
HuffmanTree Huffman(MinHeap H){
    //假设H->Size个权值已经存在H->Elements[]->Weight里
    int i;HuffmanTree T;
    BuildMinHeap(H);  //将H->Elements[]按权值调整为最小堆
    for(i=1;i<H->size;i++){ //做H->Size-1次合并
    T = malloc(sizeof(struct TreeNode)); //建立新结点    
    T->Left = DeleteMin(H); //从最小堆中删除一个结点，作为新T的左子结点
    T->Right = DeleteMin(H);    //从最小堆中删除一个结点，作为新T的右子结点
    T->Weight = T->Left->Weight+T->Right->Weight;   //计算新权值
    Insert(H,T);  //将新T插入最小堆
    }
    T = DeleteMin(H);
    return T;
}

哈夫曼树的特点

• 没有度为1的结点；
• n个叶子结点的哈夫曼树共有2n-1个节点；
• 哈夫曼树的任意非叶节点的左右子树交换后仍然是哈夫曼树；
• 对同一组权值，可能存在不同构的两颗哈夫曼树

哈夫曼树为了让字符串的编码存储空间最小，就是不等长编码。为了避免二义性可以无二义地解码，我们可以用二叉树进行编码。即左右分支为0、1，字符只在叶结点上。所以让字符编码存储空间最小就等价于构造哈夫曼树。