# 哈夫曼树

给定 n 个权值作为 n 个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。

哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。

# 哈夫曼树的构造方法

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

typedef struce TreeNode \*HuffmanTree;

struct TreeNode{
int Weight;
HuffmanTree Left, Right;
};

HuffmanTree Huffman( MinHeap H ) {

    // 假设 H->Size 个权值已经存在 H->Elements[]->Weight 里
    int i; HuffmanTree T;

    // 将 H->Elements[]按权值调整为最小堆
    BuildMinHeap(H);

    for (i = 1; i < H->Size; i++) {

        // 建立新的结点
        T = malloc(sizeof(struct TreeNode));

        // 从最小堆中删除一个结点，作为新 T 的左子结点
        T->Left = DeleteMin(H);
        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 个结点
哈夫曼树的任意非叶结点的左右子树交换后仍是哈夫曼树
对同一组{w1, w2, w3,…,wn}, 存在不同构的两颗哈夫曼树， WPL 值一样。

# 哈夫曼编码

前缀码（prefix code）：任何字符的编码都不是另一个字符编码的前缀，可以达到无二义地解码
权值：权值就是定义的路径上面的值。可以这样理解为节点间的距离。通常指字符对应的二进制编码出现的概率。