赫夫曼树及应用

最优二叉树（赫夫曼树）

路径

路径长度 树的路径长度 节点的带权路径长度 树的带权路径长度

带权路径长度 WPL 最小的二叉树称为最优二叉树或赫夫曼树(Huffman Tree)。

赫夫曼算法

赫夫曼最早给出了构建赫夫曼树的一个带有一般规律的算法，俗称赫夫曼算法，其过程如下：

(1) 根据给定的 n 个权值 { w₁,w₂,…,w_n } 构成 n 棵二叉树的集合 F = { T₁,T₂,…,T_n }，其中每棵二叉树 T_i 中只有一个带权为 w_i 的根节点；
(2) 在 F 中选取两棵根节点的权值最小的树作为左右子树构造一棵新的二叉树，且将新的二叉树根节点的权值设置为其左、右子树上根节点的权值之和。
(3) 在 F 中删除这两棵树，同时将新得到的二叉树加入 F 中；
(4) 重复 (2) 和 (3)，直到 F 只含一棵树为止。
这棵树便是赫夫曼树(Huffman Tree)。

根据这一过程可以发现，最终形成的赫夫曼树总共右 2n-1 个节点，其中 n 个叶子节点，n-1 个非终端节点，这 n-1 个节点的度均为 1，也就是说赫夫曼树中没有度为 1 的节点，这种树又称为严格的（正则的）二叉树，这种规范的结构便于赫夫曼树的存储，可以直接使用紧凑的顺序存储。

赫夫曼编码

编码长度尽可能短

不定长编码

前缀编码

二进制前缀编码

设计最短的二进制前缀编码可等效为以 n 种字符出现的频率作权，设计一棵赫夫曼树的问题，由此得到的二进制前缀编码即称为赫夫曼编码。

编码实现

因为赫夫曼树中是严格的二叉树，共有 2n-1 个节点，于是可以将其存储在大小为 2n-1 的一维数组中。
至于树节点的结构，由于在构成赫夫曼树之后，需要从叶子出发从叶子到根逆向求解编码；而进行译码时又需要从跟出发从根到叶子进行搜索，因此每个树节点既需要知道双亲信息，又需要知道孩子节点的信息。于是，赫夫曼树节点的存储结构为：

// 定义 Huffman 树节点
typedef struct
{
    unsigned int weight;
    unsigned int parent, lchild, rchild;
}HTNode, *HuffmanTree; // 动态分配数组存储 Huffman 树

// 动态分配数组存储 Huffman 编码，不定长编码，指针数组
typedef char * *HuffmanCode;

求解赫夫曼编码的代码实现如下：

// 从叶子到根，求解 Huffman 编码
// w 存放 n 个字符的权值(>0)，从叶子到根构建 Huffman 树并求得 Huffman 编码
// 也可以从根到叶子向下搜索来求编码
void HuffmanCoding(HuffmanTree *HT, HuffmanCode *HC, int *w, int n)
{
    if (n < 1) return;
    // 根据字符数量 n 分配 2n 个树节点空间（一维数组，0号未使用）
    int i, m = 2 * n -1;
    (*HT) = (HTNode *)malloc((m+1) * sizeof(HTNode));
    // 定义一个 (*HT) 树的游标指针
    HTNode *p;
    // 初始化 n 个叶子节点，0 号空间未使用，p = (*HT)+1 开始，[1~n]
    for (i = 1, p = (*HT)+1; i <= n; ++i, ++w, ++p)
    {
        (*p).weight = *w; (*p).parent = 0;
        (*p).lchild = 0; (*p).rchild = 0;
    }
    // 初始化剩下 n-1 个非终端节点，[n+1~2n-1]
    for (; i <= m; ++i, ++p) // i = n+1
    {
        (*p).weight = 0; (*p).parent = 0;
        (*p).lchild = 0; (*p).rchild = 0;
    }
    // 每次选取两个最小节点，从叶子到根建立 Huffman 树
    int min, sec;
    for (i = n+1; i <= m; ++i)
    {
        Select((*HT), &min, &sec, i-1);
        // 两个当前最小
        (*HT)[min].parent = i; (*HT)[sec].parent = i;
        // 更新根节点
        (*HT)[i].lchild = min; (*HT)[i].rchild = sec;
        (*HT)[i].weight = (*HT)[min].weight + (*HT)[sec].weight;
    }
    // 从叶子到根，逆向求每个字符的 Huffman 编码（也可以正向遍历求解）
    // n 个指针向量，不定长编码（一维数组）
    (*HC) = (HuffmanCode)malloc((n+1) * sizeof(char *));
    // 每个字符的编码的工作空间，不是编码最终存储位置
    char *cd = (char *)malloc(n * sizeof(char));
    cd[n-1] = '\0'; // 编码（字符串）结束符
    // n 个字符逆向求编码
    int start = n-1;
    int j, pa; // 当前和 parent
    for (i = 1; i <= n; ++i)
    {
        start = n-1;
        // 从叶子向根逆向求编码，j 指向当前节点，p 指向双亲；逆向搜索，所以逆着存
        for (j = i, pa = (*HT)[j].parent; pa != 0; j = pa, pa = (*HT)[pa].parent)
            if ((*HT)[pa].lchild == j) cd[--start] = '0'; // 左 0
            else cd[--start] = '1'; // 右 1
        // 不定长编码，动态分配空间
        (*HC)[i] = (char *)malloc((n-start) * sizeof(char));
        strcpy((*HC)[i], &(cd[start]));
    }
}