一、哈夫曼树：从数据压缩说起
我记得刚入行那会儿，第一次接触哈夫曼树是在一个嵌入式项目里。当时要往一块只有 64KB Flash 的芯片上塞一套字库，怎么都装不下。后来用了哈夫曼编码压缩，硬是把字库压到了 40KB 以内。嗯，从那以后我就记住了——哈夫曼树这东西，关键时刻真能救命。
说白了，哈夫曼树是一种特殊的二叉树。它不是为了查找而生的，而是为了「最优编码」而生的。你想想看，如果我们要给一堆字符设计二进制编码，怎么让总长度最短？哈夫曼树就是干这个的。
1.1 什么是哈夫曼树
先给个正式定义：哈夫曼树（Huffman Tree），也叫最优二叉树，是带权路径长度（WPL）最小的二叉树。
什么叫「带权路径长度」？我习惯用一个公式来理解：
WPL = Σ (每个叶子节点的权值 × 该节点到根节点的路径长度)举个例子。假设我们有三个叶子节点，权值分别是 2、3、5。如果把它们排成一条直线（类似链表），那 WPL 就是 2×2 + 3×2 + 5×2 = 20。但如果用哈夫曼算法构造一棵树，WPL 能降到 2×2 + 3×1 + 5×1 = 12。差距很明显吧？
核心要点：哈夫曼树追求的是「高频字符路径短，低频字符路径长」。这个思想贯穿了整个数据压缩领域。
1.2 构造哈夫曼树的算法
构造过程其实不复杂。我给大家拆解一下：
- 初始化：把所有节点看成独立的树，每棵树只有一个根节点（就是它自己）。
- 选最小的两个：从森林中选出权值最小的两棵树。
- 合并：用一个新的根节点把这两棵树连起来，新根节点的权值等于两棵子树权值之和。
- 重复：把新树放回森林，继续找最小的两棵，直到只剩一棵树。
这个过程，我建议你拿纸笔走一遍。我在项目里调试哈夫曼编码时，就经常手算一遍来验证代码逻辑。
来看代码实现：
// 哈夫曼树节点结构
typedef struct HuffmanNode {
int weight; // 权值
int parent, left, right; // 父节点和左右孩子下标
} HuffmanNode;
// 构造哈夫曼树
void buildHuffmanTree(HuffmanNode *tree, int *weights, int n) {
// 初始化所有节点
for (int i = 0; i < 2 * n - 1; i++) {
tree[i].parent = -1;
tree[i].left = -1;
tree[i].right = -1;
}
for (int i = 0; i < n; i++) {
tree[i].weight = weights[i];
}
// 循环合并
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;
}
}
}
// 合并 min1 和 min2
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;
}
}小技巧：实际编码时，我习惯用最小堆（优先队列）来优化找最小两个节点的过程。这样时间复杂度能从 O(n²) 降到 O(n log n)。
1.3 哈夫曼编码的原理
哈夫曼编码是哈夫曼树最经典的应用。原理其实很简单：
- 从根节点出发，往左走记 0，往右走记 1
- 走到叶子节点时，路径上的 0 和 1 就组成了该字符的编码
- 因为每个字符都是叶子节点，所以编码是前缀码——没有任何一个编码是另一个编码的前缀
这一点特别重要。我曾经在项目中遇到过一个问题：用了一种非前缀码的编码方案，结果解码时怎么都对不上。后来换成哈夫曼编码，问题立刻解决了。前缀码保证了「唯一可译性」，这是数据压缩的基础。
来看一个具体的例子。假设我们有 5 个字符，出现频率如下：
| 字符 | A | B | C | D | E |
|---|---|---|---|---|---|
| 频率 | 5 | 4 | 3 | 2 | 1 |
构造哈夫曼树后，得到的编码可能是：
- A: 00
- B: 01
- C: 10
- D: 110
- E: 111
你看，频率最高的 A 和 B 只用了 2 位，而频率最低的 D 和 E 用了 3 位。这就是哈夫曼编码的精髓——用最短的编码表示最常出现的内容。
注意：哈夫曼编码不是唯一的。同样的频率分布，如果合并时选择不同的两个最小节点，或者左右子树交换位置，都会得到不同的编码树。但它们的 WPL 是一样的，都是最优的。
1.4 知识体系总览
下面这张图是我自己整理的哈夫曼树知识结构，方便你快速把握全局：
这张图把哈夫曼树的三个核心方面串起来了。我个人建议你从「定义」入手，理解 WPL 的概念，然后看「构造算法」怎么实现，最后再理解「编码」是怎么从树里提取出来的。这个顺序学起来最顺。
好了，哈夫曼树的上半部分就讲到这里。下一节我们会深入讨论哈夫曼编码的具体实现、解码过程，以及它在实际项目中的应用场景。到时候我会分享一些我在压缩工具开发中踩过的坑，希望对你有帮助。
公众号:蓝海资料掘金营，微信deep3321