18. 赫夫曼树：从定义到编码，一个压缩算法的核心

赫夫曼树，也叫最优二叉树。说实话，我第一次听到这个名字时，觉得它很高深。后来在项目中做数据压缩，才真正体会到它的巧妙。说白了，它就是一棵带权路径长度最短的二叉树。

嗯，咱们先别急着看代码。先理解它为什么叫“最优”。

18.1 赫夫曼树的定义

先看几个关键概念：

• 路径长度：从一个结点到另一个结点的分支数。比如根到第三层结点，路径长度就是2。
• 带权路径长度（WPL）：每个叶子结点的权值 × 它的路径长度，然后求和。
• 赫夫曼树：WPL 最小的二叉树。

我举个例子你就明白了。假设有四个字符：A、B、C、D，出现频率分别是 5、7、2、4。如果随便建一棵树，WPL 可能很大。但赫夫曼树能保证 WPL 最小。

为什么会这样？你想想看，权值大的结点如果离根远，路径长度就大，乘积自然就大。所以我们要把高频的字符放在靠近根的位置。

18.2 赫夫曼树的构造

构造过程其实不复杂。我习惯用一句话概括：每次从森林中选两棵权值最小的树合并。

具体步骤：

1. 把所有结点看成独立的树（森林）。
2. 选两个权值最小的根结点，合并成一棵新树。
3. 新树的权值 = 两个子树的权值之和。
4. 把新树放回森林，重复步骤2-3，直到只剩一棵树。

来看个例子。还是刚才的 A(5)、B(7)、C(2)、D(4)：

第一步：选 C(2) 和 D(4)，合并成新结点 E(6)
第二步：选 A(5) 和 E(6)，合并成 F(11)
第三步：选 B(7) 和 F(11)，合并成 G(18)

最终树的结构：

        G(18)
       /    \
     B(7)   F(11)
           /    \
         A(5)   E(6)
               /   \
             C(2)  D(4)

计算 WPL：7×1 + 5×2 + 2×3 + 4×3 = 7 + 10 + 6 + 12 = 35。这是最小的。

下面我用 C 语言实现一下核心逻辑：

// 赫夫曼树结点结构
typedef struct {
    int weight;       // 权值
    int parent;       // 父结点下标
    int left, right;  // 左右孩子下标
} HuffmanNode;

// 构造赫夫曼树
void buildHuffmanTree(HuffmanNode *tree, int n) {
    // 初始化所有结点
    for (int i = 0; i < 2 * n - 1; i++) {
        tree[i].parent = -1;
        tree[i].left = -1;
        tree[i].right = -1;
    }

    // 循环 n-1 次，每次合并两个最小权值结点
    for (int i = n; i < 2 * n - 1; i++) {
        int min1 = -1, min2 = -1;

        // 找两个最小的无父结点
        for (int j = 0; j < i; j++) {
            if (tree[j].parent == -1) {
                if (min1 == -1 || tree[j].weight < tree[min1].weight) {
                    min2 = min1;
                    min1 = j;
                } else if (min2 == -1 || tree[j].weight < tree[min2].weight) {
                    min2 = j;
                }
            }
        }

        // 合并
        tree[i].weight = tree[min1].weight + tree[min2].weight;
        tree[i].left = min1;
        tree[i].right = min2;
        tree[min1].parent = i;
        tree[min2].parent = i;
    }
}

18.3 赫夫曼编码

树建好了，编码就简单了。从根到叶子，左分支记 0，右分支记 1。路径上的 0 和 1 串起来就是该字符的编码。

还是刚才的例子：

字符	权值	编码
B	7	0
A	5	10
C	2	110
D	4	111

注意看，没有哪个编码是另一个编码的前缀。这就是前缀编码的特性。解码时不会产生歧义。

编码生成的代码：

// 从叶子向上回溯，生成编码
void getHuffmanCode(HuffmanNode *tree, int n, char **codes) {
    char *temp = (char *)malloc(n * sizeof(char));
    temp[n - 1] = '\0';

    for (int i = 0; i < n; i++) {
        int start = n - 1;
        int current = i;
        int parent = tree[i].parent;

        while (parent != -1) {
            if (tree[parent].left == current) {
                temp[--start] = '0';
            } else {
                temp[--start] = '1';
            }
            current = parent;
            parent = tree[parent].parent;
        }

        codes[i] = (char *)malloc((n - start) * sizeof(char));
        strcpy(codes[i], &temp[start]);
    }

    free(temp);
}

18.4 知识体系总览

下面这张图帮你理清本章的核心逻辑：

你看，整个知识体系其实就三个环：定义告诉你“是什么”，构造告诉你“怎么做”，编码告诉你“有什么用”。

18.5 几个容易忽略的细节

• 赫夫曼树不唯一：左右子树可以互换，但 WPL 相同。
• 没有度为1的结点：赫夫曼树只有度为0和度为2的结点。
• 编码是变长的：高频字符编码短，低频字符编码长。这就是压缩的原理。

好了，赫夫曼树的内容就这些。代码不多，但思想很巧妙。你写代码时多跑几个例子，很快就能掌握。

---

公众号:蓝海资料掘金营，微信deep3321