Appearance
哈夫曼树
为什么需要哈夫曼树
在数据通信和文件压缩中，不同字符出现的频率往往差别很大。如果对所有字符都采用等长编码，会造成大量空间浪费。哈夫曼树（最优二叉树）的思想是：让出现频率高的字符使用短编码，频率低的字符使用长编码，从而使总编码长度最短。
408 考研中，哈夫曼树是树与二叉树章节的重点，涉及 WPL 计算、构建算法和哈夫曼编码，选择题和应用题均高频出现。
核心思想
带权路径长度（WPL, Weighted Path Length）：树中所有叶结点的权值与其到根结点路径长度的乘积之和。
$$WPL = \sum_{i=1}^{n} w_i \times l_i$$
其中 $w_i$ 是第 i 个叶结点的权值，$l_i$ 是该叶结点到根的路径长度（经过的边数）。
哈夫曼树的核心特点：
- WPL 最小：在所有含 n 个叶结点、权值相同的二叉树中，哈夫曼树的 WPL 最小
- 贪心策略：每次选取权值最小的两棵树合并，保证权值大的叶结点离根更近
- 没有度为 1 的结点：哈夫曼树中只存在度为 0（叶结点）和度为 2 的结点
- 结点总数：n 个叶结点的哈夫曼树共有 2n - 1 个结点（n - 1 个内部结点）
交互可视化
通过下方的交互动画，你可以逐步观察哈夫曼树的执行过程：
操作详解
构建过程
哈夫曼树的构建采用贪心算法，步骤如下：
- 将 n 个权值分别作为 n 棵只有根结点的二叉树，构成森林 F
- 从 F 中选取权值最小的两棵树作为左右子树，合并为一棵新树，新树根的权值 = 左右子树权值之和
- 从 F 中删除被选中的两棵树，将新树加入 F
- 重复步骤 2-3，直到 F 中只剩一棵树，即为哈夫曼树
示例：给定权值集合 {2, 3, 5, 7}，构建过程如下：
第1步: 选最小的 2 和 3，合并为 5
5
/ \
2 3
第2步: 选最小的 5(新) 和 5(原)，合并为 10
10
/ \
5 5
/ \
2 3
第3步: 选 10 和 7，合并为 17
17
/ \
10 7
/ \
5 5
/ \
2 3构建算法的 C 语言实现：
c
typedef struct {
int weight; // 权值
int parent; // 父结点下标
int lchild; // 左孩子下标
int rchild; // 右孩子下标
} HTNode;
// 构建哈夫曼树，w[] 为权值数组，n 为叶结点数
void CreateHuffmanTree(HTNode ht[], int w[], int n) {
int total = 2 * n - 1; // 总结点数
// 初始化所有结点
for (int i = 0; i < total; i++) {
ht[i].parent = ht[i].lchild = ht[i].rchild = -1;
ht[i].weight = (i < n) ? w[i] : 0;
}
// 进行 n-1 次合并
for (int i = n; i < total; i++) {
int min1 = -1, min2 = -1;
// 在没有父结点的结点中，选权值最小的两个
for (int j = 0; j < i; j++) {
if (ht[j].parent != -1) continue;
if (min1 == -1 || ht[j].weight < ht[min1].weight) {
min2 = min1;
min1 = j;
} else if (min2 == -1 || ht[j].weight < ht[min2].weight) {
min2 = j;
}
}
// 合并 min1 和 min2
ht[i].weight = ht[min1].weight + ht[min2].weight;
ht[i].lchild = min1;
ht[i].rchild = min2;
ht[min1].parent = ht[min2].parent = i;
}
}哈夫曼编码
哈夫曼编码是一种前缀编码——任何一个字符的编码都不是另一个字符编码的前缀，因此解码时不会产生歧义。
编码规则：从根到叶结点的路径上，走左分支记 0，走右分支记 1（也可反过来，但需保持一致），路径上的 0/1 序列即为该叶结点对应字符的编码。
示例：权值 {2, 3, 5, 7} 对应字符 {D, C, B, A}，由上面的哈夫曼树得到编码：
| 字符 | 权值 | 编码 | 编码长度 |
|---|---|---|---|
| A | 7 | 1 | 1 |
| B | 5 | 01 | 2 |
| C | 3 | 001 | 3 |
| D | 2 | 000 | 3 |
前缀编码的性质：哈夫曼编码中，每个编码对应哈夫曼树的一个叶结点。由于叶结点不可能是其他叶结点到根路径上的中间结点，所以天然满足前缀编码的要求。
WPL 计算
WPL 等于所有叶结点的 "权值 × 路径长度" 之和，也等于所有非叶结点权值之和（这是一个常用的等价计算技巧）。
以上面的例子为例：
WPL = 7×1 + 5×2 + 3×3 + 2×3
= 7 + 10 + 9 + 6
= 32
等价计算: 非叶结点权值之和 = 17 + 10 + 5 = 32 ✓WPL 的实际含义：若将权值视为字符出现次数，WPL 就是用该编码方案编码所有字符所需的总比特数。哈夫曼树保证这个总数最小。
复杂度分析
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| 构建哈夫曼树 | O(n²) | n-1 次合并，每次线性查找最小值 |
| 构建哈夫曼树（优化） | O(n log n) | 使用最小堆（优先队列）选最小值 |
| 生成哈夫曼编码 | O(n log n) | 每个叶结点回溯到根，平均路径长度 O(log n) |
空间复杂度：O(n)，需要 2n - 1 个结点的存储空间。
考研高频考点
- ⭐ 给定权值，画出哈夫曼树并求 WPL（应用题必考）
- ⭐ 哈夫曼编码的编码/解码过程（选择题、应用题高频）
- ⭐ 哈夫曼树的性质：无度为 1 的结点，n 个叶结点共 2n-1 个结点（选择题高频）
- ⭐ 前缀编码的概念及判定方法（选择题）
- WPL 的定义与计算（填空题、选择题）
- 哈夫曼树不唯一，但 WPL 唯一（易错点）
- 哈夫曼编码是最优前缀编码，但不是唯一的最优编码（概念辨析）