求哈夫曼编码时，先把每个字符按出现次数做成节点，每次选两个频率最低的节点合并成新的父节点，反复合并，最终形成一棵树；再从根节点出发，给左枝标0、右枝标1，叶节点到根的路径串起来就是该字符的编码。按这套流程，高频字符靠近树根、编码短，低频字符靠近树梢、编码长，整体平均码长更紧凑。
核心方法
- • 先统计字符频率。
- • 再把频率作为权重合并节点。
- • 最后沿树读取01串。
原理说明
哈夫曼编码把出现次数当作权重。权重大的字符路径短，权重小的字符路径长。合并时优先选权重最低的两个节点，让它们位于树的底层，整体加权路径长度更短。编码表中的0和1组合形成前缀编码，解码时沿树逐位走即可定位字符。
操作流程
| 序号 | 动作 | 要点 |
|---|---|---|
| 1 | 统计频率 | 列出字符和出现次数 |
| 2 | 建初始节点 | 每个字符对应一个节点，节点权重为频率 |
| 3 | 选最低节点 | 从当前节点中选权重最低的两个 |
| 4 | 合并父节点 | 新节点权重为两者相加 |
| 5 | 放回节点池 | 新节点进入待合并列表 |
| 6 | 继续合并 | 列表留下一个根节点时进入读码阶段 |
| 7 | 给枝干标号 | 左枝标0，右枝标1，也可交换 |
| 8 | 读取路径 | 从根走到叶，记录沿途的0和1 |
示例演算
| 字符 | 频率 |
|---|---|
| A | 5 |
| B | 9 |
| C | 12 |
| D | 13 |
| E | 16 |
| F | 45 |
合并过程
| 轮次 | 当前选择 | 合并结果 | 合并后节点集合 |
|---|---|---|---|
| 1 | A 5、B 9 | AB 14 | C 12、D 13、E 16、AB 14、F 45 |
| 2 | C 12、D 13 | CD 25 | E 16、AB 14、CD 25、F 45 |
| 3 | AB 14、E 16 | ABE 30 | CD 25、ABE 30、F 45 |
| 4 | CD 25、ABE 30 | CDEAB 55 | F 45、CDEAB 55 |
| 5 | F 45、CDEAB 55 | ROOT 100 | ROOT 100 |
读取结果
| 字符 | 一种哈夫曼编码 | 码长 |
|---|---|---|
| F | 0 | 1 |
| C | 100 | 3 |
| D | 101 | 3 |
| E | 111 | 3 |
| A | 1100 | 4 |
| B | 1101 | 4 |
使用提示
这套流程适合字符频率分布清晰的数据表示。构建时记录每一轮合并关系，后续读取编码更稳。同一组频率可生成多种等价树形，只要合并顺序与左右标号规则保持清楚，编码表即可使用。
免责声明：本文为通用技术说明，具体应用可结合场景选择。
