🌳 哈夫曼树与编码
所属等级：GESP 6级 ｜ 难度： ｜ 关键词：哈夫曼树、WPL、贪心、前缀码、数据压缩
📝 考纲要求
- 理解哈夫曼树的概念：带权路径长度（WPL）最小的二叉树；
- 掌握贪心构建方法：每次从森林里取出权值最小的两棵树合并；
- 理解哈夫曼编码：约定左分支为 0、右分支为 1，得到的是前缀码（无歧义、可唯一解码）；
- 了解哈夫曼编码在数据压缩中的应用：出现频率越高的字符，编码越短。
📖 通俗讲解
💡 一句话理解
哈夫曼树就是“最省总长度”的一棵树：把权值大的叶子放在离根更近（更短）的位置，权值小的放在更远（更长）的位置，让所有“叶子权值 × 到根距离”的总和最小。
比如有 5 个字符，出现的次数（权值）分别是 2、3、5、7、11。我们一开始把它们看成 5 棵孤零零的小树（一个森林）。贪心的意思是：每一步都挑“当前最轻的两棵”合并成一棵新树，新树的权值是两者之和。重复这个过程，最后只剩一棵树，就是哈夫曼树。
🖼️ 图解
建立哈夫曼树：权值 A:5 B:2 C:1 D:3
森林(初始)： [A5] [B2] [C1] [D3]
第1步：最小两个 C1 + B2 -> 新节点3
[A5] [D3] [ 3 ] (3 = C+B)
/ \
C1 B2
第2步：最小两个 D3 + 3 -> 新节点6
[A5] [ 6 ] (6 = D + (C+B))
/ \
D3 3
/ \
C1 B2
第3步：最后 A5 + 6 -> 根11，得到哈夫曼树
11
/ \
A5 6
/ \
D3 3
/ \
C1 B2
左0右1 编码： A=0 D=10 C=110 B=111
频率越高(A)编码越短，频率越低(B,C)编码越长。🌲 森林合并过程（ASCII 图解）
合并过程
初始森林（每片叶子都是一棵单独的树）：
[2] [3] [5] [7] [11]
第1步：最小的两棵是 2 和 3，合并 -> 新树权值 5
[5] [5] [7] [11]
^2+3
第2步：最小的两棵是 5 和 5，合并 -> 新树权值 10
[7] [10] [11]
^5+5
第3步：最小的两棵是 7 和 10，合并 -> 新树权值 17
[11] [17]
^7+10
第4步：最后合并 11 和 17 -> 根 28，得到哈夫曼树
[28]
^11+17🌳 最终哈夫曼树（左 0 右 1）
树结构
28
/ \
11 17
/ \
7 10
/ \
5 5
/ \
2 3
约定：从根往下的「左分支」记 0，「右分支」记 1从根到每个叶子的路径拼起来就是它的编码：11 在左枝 → 0；7 在“右-左” → 10；5 在“右-右-左” → 110；2、3 在“右-右-右” → 1110 和 1111。频率最高（11）的字符编码最短，这正是压缩的关键。
📦 为什么能压缩
真实文本里，像字母
e、空格出现得很多，给它们短编码，给罕见字符长编码，整段文字的平均长度就变小了。哈夫曼编码是很多压缩格式（如 ZIP、图片）的核心思想之一。
🔵 核心必背重点
✅ 必背
- WPL（带权路径长度）：WPL = Σ(叶子权值 × 路径长度)，即每个叶子权值乘它到根经过的边数，再加总；
- 哈夫曼树：在所有可能的二叉树中，WPL 最小的那一棵；
- 贪心合并：每次取权值最小的两棵树合并，新树权值 = 两树权值之和；
- 哈夫曼编码：左分支 0、右分支 1；因为没有任何字符的编码是另一个字符编码的前缀，所以叫前缀码，解码时不会混淆；
- WPL 速算：把所有“合并产生的新节点权值”加起来，就是 WPL（本例 5+10+17+28 = 60）。
🔑
记忆口诀：“轻的抱团往下沉，重的靠近根上挂；左 0 右 1 标路径，前缀编码不打架。”
🔴 考试拉分难点
⚠️ 难点
- 合并时“找最小两个”：必须用最小堆（优先队列）或反复扫描找最小的两个，不能直接排序一次就完事，因为每次合并后森林会变化；
- WPL 计算：容易把“路径长度”数错（根到叶子经过的边数，根本身不算长度）；
- 编码不唯一：左右孩子谁当 0 谁当 1 不影响 WPL，所以不同写法都对，但同一份答案内部要前后一致；
- 相同权值的处理：出现相等权值时，任选两个合并即可，最终 WPL 一定相同。
🟡 高频易错陷阱
🚫 扣分坑点
- 把“路径长度”当成“层数”算多 1（根到叶子若经过 3 条边，长度是 3，不是 4）；
- 合并时忘记把新树重新放回森林，导致森林数量没减少、死循环；
- 误以为哈夫曼编码需要等长（其实它不等长，正是靠不等长来省空间）；
- 用普通数组排序代替最小堆，合并后没更新集合，结果算错 WPL；
- 解码时把前缀码当成普通编码，没利用“前缀无歧义”的特性。
🧪 例题演练
例题 1（基础题）：求哈夫曼树的 WPL
题目：给定叶子权值 2、3、5、7、11，用贪心法构建哈夫曼树，求带权路径长度 WPL。
C++
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
struct Node {
int w; // 权值
Node *l, *r; // 左右孩子
Node(int w) : w(w), l(nullptr), r(nullptr) {}
};
// 最小堆：权值小的优先出队
struct Cmp {
bool operator()(Node* a, Node* b) { return a->w > b->w; }
};
// 递归计算 WPL = Σ(叶子权值 × 路径长度)
int wpl(Node* p, int depth) {
if (!p) return 0;
if (!p->l && !p->r) return p->w * depth; // 叶子
return wpl(p->l, depth + 1) + wpl(p->r, depth + 1);
}
int main() {
int a[] = {2, 3, 5, 7, 11};
int n = 5;
priority_queue<Node*, vector<Node*>, Cmp> pq;
for (int i = 0; i < n; i++) pq.push(new Node(a[i]));
// 反复合并权值最小的两棵树
while (pq.size() > 1) {
Node* x = pq.top(); pq.pop();
Node* y = pq.top(); pq.pop();
Node* root = new Node(x->w + y->w); // 新树权值 = 两子树之和
root->l = x; root->r = y;
pq.push(root);
}
cout << "WPL = " << wpl(pq.top(), 0) << endl;
return 0;
}输出WPL = 60
✅ 手算核对
合并产生的内部节点权值依次为 5、10、17、28，相加 5+10+17+28 = 60，与程序一致。
例题 2（模拟真题）：构造哈夫曼编码
题目：字符 a、b、c、d、e 的出现频率分别为 2、3、5、7、11。构造哈夫曼树并输出每个字符的编码（左 0 右 1），指出频率最高的字符编码是什么。
C++
#include <iostream>
#include <queue>
#include <vector>
#include <string>
using namespace std;
struct Node {
int w;
char ch; // 原字符，非叶子记为 '\0'
Node *l, *r;
Node(int w, char c = '\0') : w(w), ch(c), l(nullptr), r(nullptr) {}
};
struct Cmp {
bool operator()(Node* a, Node* b) { return a->w > b->w; }
};
// 递归输出编码：左分支记 '0'，右分支记 '1'
void printCode(Node* p, string s) {
if (!p) return;
if (p->ch != '\0') { // 到达叶子 = 原字符
cout << p->ch << " : " << (s.empty() ? "0" : s) << endl;
return;
}
printCode(p->l, s + '0');
printCode(p->r, s + '1');
}
int main() {
char ch[] = {'a','b','c','d','e'};
int freq[]= { 2, 3, 5, 7, 11};
int n = 5;
priority_queue<Node*, vector<Node*>, Cmp> pq;
for (int i = 0; i < n; i++) pq.push(new Node(freq[i], ch[i]));
while (pq.size() > 1) { // 同例题1的贪心合并
Node* x = pq.top(); pq.pop();
Node* y = pq.top(); pq.pop();
Node* root = new Node(x->w + y->w);
root->l = x; root->r = y;
pq.push(root);
}
printCode(pq.top(), "");
return 0;
}输出e : 0
d : 10
c : 110
a : 1110
b : 1111
📌 结论
频率最高的
e（11 次）编码最短，只有 0；频率最低的 a、b 编码最长（1110、1111）。这些编码互为前缀码，解码时从根沿 0/1 走到底即可唯一确定字符。
🛡️ 避坑总结
- 哈夫曼树＝WPL 最小的二叉树，用贪心每次合并最轻的两棵；
- 路径长度是根到叶子经过的边数，别多数一层；
- WPL 可速算：把所有合并出的内部节点权值相加；
- 编码约定左 0 右 1，得到的是无歧义的前缀码；
- 频率高的字符编码短，这正是哈夫曼编码能压缩数据的原因；
- 实现时优先用最小堆（优先队列），合并后记得把新树放回集合。
💡 提示：按 ← → 方向键可在上一 / 下一知识点间快速翻页