Appearance
哈夫曼树与哈夫曼编码
概念
哈夫曼树（Huffman Tree，又称最优二叉树）是指：给定 n 个带权值的叶子结点，构造出的带权路径长度 WPL 最小的二叉树。
先明确三个长度概念（从根往下数，根在第 0 层）：
| 概念 | 定义 |
|---|---|
| 路径长度 | 从根到该结点所经过的边数 |
| 结点的带权路径长度 | 该结点的权值 × 它的路径长度 |
| 树的带权路径长度 WPL |
一句话理解：让权值大的叶子尽量靠近根、权值小的叶子尽量远离根，这棵树的 WPL 就最小——哈夫曼算法就是一个"每次抓两个最小的合并"的贪心过程。
原理
哈夫曼算法（贪心）
对权值集合
- 把每个权值看作一棵只有一个结点的树，放进森林；
- 从森林中选出根权值最小的两棵树，合并成一棵新树：新树根的权值 = 两棵子树根权之和，两棵子树分别作为它的左、右孩子；
- 把新树放回森林，重复步骤 2，直到森林中只剩一棵树。
三条必考性质
| # | 性质 | 说明 |
|---|---|---|
| 1 | 没有度为 1 的结点 | 每次合并都是"两个变一个"，所以分支结点度恒为 2。故它是正则二叉树（严格二叉树） |
| 2 | n 个叶子 → 共 2n − 1 个结点 | 由性质 1 推得：设度为 2 的结点数为 |
| 3 | WPL = 所有分支结点权值之和 | 也就是合并过程中每次产生的那个新权值之和。这给出了不用画树就能算 WPL 的捷径 |
记忆：性质 3 是解题利器——题目只给权值集合求 WPL 时，直接写"每次合并的和"再相加，比画完树再逐叶乘层数快得多，也不容易漏。
哈夫曼树不唯一，但 WPL 唯一
当存在权值相等的结点时，选哪两个先合并、谁是左谁是右，都会产生不同的树形（也产生不同的编码），但最小 WPL 是唯一的。
哈夫曼编码
把哈夫曼树用到通信上：
- 每个字符是一个叶子（权 = 出现频度/次数）；
- 从根到该叶子的路径上，左分支记 0、右分支记 1（或反之，约定即可），得到的 01 串就是该字符的哈夫曼编码。
它是前缀编码（Prefix Code）：任何一个字符的编码都不是另一个字符编码的前缀。原因是所有字符都在叶子上，从根到叶子的路径不可能经过另一个叶子。
前缀编码的价值在于译码无歧义：拿到比特流后从根开始走，走到叶子就输出一个字符并回到根，不需要任何分隔符。
对比：若用定长编码，n 个字符需要
位；哈夫曼编码是不等长的，高频字短、低频字长，总位数更少。
示例
例一：4 个权值，求最小 WPL
给定权值集合 {7, 5, 2, 4}，构造哈夫曼树并求 WPL。
完整推导过程：
第一步，排序后取最小两个：2 与 4 → 合并得 6。剩余 {5, 6, 7}。
第二步，取最小两个：5 与 6 → 合并得 11。剩余 {7, 11}。
第三步，取最后两个：7 与 11 → 合并得 18。完成。
18 ← 第三步：7 + 11
/ \
(7) 11 ← 第二步：5 + 6
/ \
(5) 6 ← 第一步：2 + 4
/ \
(2) (4)第四步，用捷径（性质 3）算 WPL——把每次合并产生的新权值相加：
第五步，用定义验算：7 在第 1 层、5 在第 2 层、2 和 4 在第 3 层：
顺带：本例叶子数 n = 4，总结点数 = 2n − 1 = 7。可以数一数上图的结点，正是 7 个（3 个分支 + 4 个叶子）。
例二：字符频度 → 哈夫曼编码 → 压缩率
某报文只含 6 个字符 A/B/C/D/E/F，出现次数分别为 45、13、12、16、9、5（共 100 次）。设计哈夫曼编码，求 WPL、平均码长与相对定长编码的压缩率。
完整推导过程：
第一步，列出初始森林（按次数升序）：F(5)，E(9)，C(12)，B(13)，D(16)，A(45)。
第二步，逐次合并（每次取最小的两个）：
| 轮次 | 取出的两棵 | 新根权值 |
|---|---|---|
| 1 | F(5) + E(9) | 14 |
| 2 | C(12) + B(13) | 25 |
| 3 | 14 + D(16) | 30 |
| 4 | 25 + 30 | 55 |
| 5 | A(45) + 55 | 100 |
第三步，画出哈夫曼树（约定左 = 0，右 = 1，较小的做左子树）：
100
/ \
A(45) 55
/ \
25 30
/ \ / \
C(12) B(13) 14 D(16)
/ \
F(5) E(9)第四步，读出各字符编码（根 → 叶子）：
| 字符 | 次数 | 编码 | 码长 |
|---|---|---|---|
| A | 45 | 0 | 1 |
| C | 12 | 100 | 3 |
| B | 13 | 101 | 3 |
| D | 16 | 111 | 3 |
| F | 5 | 1100 | 4 |
| E | 9 | 1101 | 4 |
第五步，算 WPL（两种算法互相验证）：
第六步，算平均码长与压缩率。100 个字符共需 224 位：
定长编码需
结论：哈夫曼编码把这段报文从 300 位压到 224 位，节省约四分之一。频度分布越悬殊（如 A 占绝大多数），压缩效果越明显。
C 语言：静态数组构造哈夫曼树并生成编码
#include <stdio.h>
#define N 6 /* 字符个数（叶子数） */
#define M (2 * N - 1) /* 总结点数：2n-1 */
typedef struct {
int weight;
int parent, lchild, rchild;
} HTNode;
HTNode ht[M];
/* 构造哈夫曼树：w 为 n 个叶子的权值 */
void buildHuffman(const int w[], int n) {
for (int i = 0; i < 2 * n - 1; i++) {
ht[i].weight = 0;
ht[i].parent = ht[i].lchild = ht[i].rchild = -1;
}
for (int i = 0; i < n; i++) ht[i].weight = w[i];
for (int i = n; i < 2 * n - 1; i++) {
int s1 = -1, s2 = -1; /* 权值最小的两个，且未合并过 */
for (int j = 0; j < i; j++) {
if (ht[j].parent != -1) continue;
if (s1 == -1 || ht[j].weight < ht[s1].weight) { s2 = s1; s1 = j; }
else if (s2 == -1 || ht[j].weight < ht[s2].weight) { s2 = j; }
}
ht[s1].parent = ht[s2].parent = i;
ht[i].lchild = s1; ht[i].rchild = s2;
ht[i].weight = ht[s1].weight + ht[s2].weight;
}
}
/* 从叶子回溯到根，再把 01 串倒过来 */
void genCode(int n, char code[][N]) {
for (int i = 0; i < n; i++) {
char tmp[N];
int k = 0, c = i, p = ht[i].parent;
while (p != -1) {
tmp[k++] = (ht[p].lchild == c) ? '0' : '1';
c = p; p = ht[p].parent;
}
for (int j = 0; j < k; j++) code[i][j] = tmp[k - 1 - j];
code[i][k] = '\0';
}
}
int main(void) {
int w[N] = {45, 13, 12, 16, 9, 5};
char ch[N] = {'A', 'B', 'C', 'D', 'E', 'F'};
char code[N][N];
buildHuffman(w, N);
genCode(N, code);
int wpl = 0, branchSum = 0;
for (int i = 0; i < N; i++) {
int len = 0; while (code[i][len]) len++;
wpl += w[i] * len;
printf("%c(%2d): %s\n", ch[i], w[i], code[i]);
}
for (int i = N; i < M; i++) branchSum += ht[i].weight; /* 性质 3：分支结点权之和 */
printf("WPL = %d, 分支结点权之和 = %d\n", wpl, branchSum); /* 224 224 */
printf("平均码长 = %.2f 位，定长 3 位共 %d 位，压缩率 %.1f%%\n",
wpl / 100.0, 300, (300 - wpl) / 300.0 * 100);
return 0;
}
c 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行
Python 对照
import heapq
def huffman(weights):
"""weights: {字符: 频度}，返回 (编码表, WPL)"""
heap, cnt = [], 0
for ch, w in weights.items():
cnt += 1
heap.append((w, cnt, {'ch': ch, 'l': None, 'r': None}))
heapq.heapify(heap)
merges = []
while len(heap) > 1:
wa, _, a = heapq.heappop(heap)
wb, _, b = heapq.heappop(heap)
cnt += 1
merges.append(wa + wb) # 记录每次合并的权
heapq.heappush(heap, (wa + wb, cnt, {'ch': None, 'l': a, 'r': b}))
root = heap[0][2]
codes = {}
def walk(t, bits):
if t['ch'] is not None:
codes[t['ch']] = bits or '0' # n=1 的退化情形
return
walk(t['l'], bits + '0'); walk(t['r'], bits + '1')
walk(root, '')
wpl = sum(weights[c] * len(codes[c]) for c in codes)
return codes, wpl, merges
w = {'A': 45, 'B': 13, 'C': 12, 'D': 16, 'E': 9, 'F': 5}
codes, wpl, merges = huffman(w)
for c in sorted(codes, key=lambda x: -w[x]):
print(f"{c}({w[c]:2d}): {codes[c]}")
print("WPL =", wpl, " 分支结点权之和 =", sum(merges)) # 224 224
print("平均码长 =", wpl / sum(w.values()), " 定长 3 位 =", sum(w.values()) * 3)
# 译码演示：前缀编码可无歧义还原
bitstream = ''.join(codes[c] for c in "FACE")
table = {v: k for k, v in codes.items()}
out, buf = '', ''
for b in bitstream:
buf += b
if buf in table: out += table[buf]; buf = ''
print("FACE ->", bitstream, "-> 还原:", out) # FACE
python 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行
考点
考点
1. 必背结论
- 哈夫曼树中不存在度为 1 的结点。
- n 个叶子 → 总结点 2n − 1 个，合并 n − 1 次。
- WPL = 所有分支结点权值之和 = 合并过程中每次新权值之和。
- 哈夫曼编码是前缀编码，译码唯一、无需分隔符。
- 哈夫曼树不唯一（等权时），但最小 WPL 唯一。
- 构造过程用最小堆（优先队列）可以做到
2. 解题套路
- 只求 WPL：不必画树，直接排序、两两合并，把每次的合并值累加。
- 求编码：画树后从根走到叶子，注意题目是否有"左 0 右 1"的约定——没约定就自己写清楚约定，左右互换只是 0/1 镜像，WPL 不变。
- 求压缩率：
3. 易错点
- "最优二叉树"指哈夫曼树，不是平衡二叉树（AVL）。这两个"最优"含义完全不同：一个是 WPL 最小，一个是树高最小。
- 路径长度是边数，根在第 0 层（部分教材把根记作第 1 层，此时路径长度 = 层数 − 1，两者差 1，务必和自己的 WPL 定义一致）。
- WPL 只对叶子求和，不要算上分支结点（捷径算法里加的是分支结点的权值，不是路径长度，别混淆）。
- 编码长度最长不超过 n − 1（n 为字符数），因为树高上界是 n − 1。
- 哈夫曼编码不等长，因此不能随机访问第 k 个字符，必须从头顺序译码——这是它的代价。
- 题目问"最少比较次数""最优判定"时往往是哈夫曼模型的变体，认准"每次取两个最小合并"即可。
小结
- 哈夫曼树使 WPL 最小，构造法就是反复"取两个最小的合并"，n 个叶子得 2n−1 个结点。
- WPL 的捷径算法（分支结点权值之和）是本章最快的得分手段。
- 哈夫曼编码是前缀编码：高频短、低频长，代价是不支持随机访问。
- 下一步：回到"集合"这种更简单的结构，看并查集如何用数组解决连通性问题。
下一篇：并查集
评论（0）
当前浏览器不允许本地存储，评论无法保存。
还没有评论，来说两句。