哈夫曼编码计算详解
——以字符集{A,B,C,D,E}的频率分布为例
一、问题描述
给定字符频率：
* a: 10%
* b: 15%
* c: 30%
* d: 16%
* e: 29%
构建哈夫曼树，计算字母d的哈夫曼编码长度。
二、哈夫曼树构建过程
核心原则：每次合并权值最小的两个节点，生成新父节点。
步骤分解：
1. 初始化节点（按权值升序排列）：
a(10), b(15), d(16), e(29), c(30)
2. 第1次合并：取最小两个节点 a(10) 和 b(15)
→ 生成新节点 ab(25)（权值=10+15）
新节点集：d(16), ab(25), e(29), c(30)
3. 第2次合并：取最小两个节点 d(16) 和 ab(25)
→ 生成新节点 dab(41)（权值=16+25）
新节点集：e(29), c(30), dab(41)
4. 第3次合并：取最小两个节点 e(29) 和 c(30)
→ 生成新节点 ec(59)（权值=29+30）
新节点集：dab(41), ec(59)
5. 第4次合并：合并最后两个节点 dab(41) 和 ec(59)
→ 生成根节点 root(100)（权值=41+59）
最终哈夫曼树结构：
三、各字符编码计算：
> 假定：向左走为0，向右走为1（实际以题目为准）
1. d(16) 的路径：
root → 左到dab → 左到d
→ 编码：00 → 长度=2
2. a(10) 的路径：
root → 左到dab → 右到ab → 左到a
→ 编码：010 → 长度=3
3. b(15) 的路径：
root → 左到dab → 右到ab → 右到b
→ 编码：011 → 长度=3
4. e(29) 的路径：
root → 右到ec → 左到e
→ 编码：10 → 长度=2
5. c(30) 的路径：
root → 右到ec → 右到c
→ 编码：11 → 长度=2
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
