哈夫曼树

**哈夫曼树（Huffman Tree）**是带权路径长度（WPL）最短的二叉树，常用于构造最优前缀编码（哈夫曼编码），例如经典的数据压缩思想实验。

本文解决什么问题

• 什么是 WPL
• 如何用贪心构造哈夫曼树
• 编码为何具有前缀性质
• 和小例子手算

带权路径长度

设叶结点权值为 $w_i$，根到该叶的路径长度为 $l_i$（边数），则：

$$WPL = \sum_i w_i \cdot l_i$$

哈夫曼树使给定权值集合下的 WPL 最小（在二叉树、权值在叶上的常见设定下）。

构造思路（贪心）

1. 把每个权值看成一棵只有根的树，放入集合
2. 反复取出权值最小的两棵树，合并为新树（根权值 = 二者之和）
3. 新树放回集合，直到只剩一棵

这正是 贪心法 的典型例子：每步合并当前最小的两个。

手算例子

权值：2, 3, 5, 7（示意）

1. 合并 2 与 3 → 新根 5；集合变为 5, 5, 7
2. 合并两个 5 → 新根 10；集合变为 7, 10
3. 合并 7 与 10 → 根 17

具体左右孩子安排、相同权值谁先取，可能产生不同形态，但 WPL 最优值相同（形态不唯一时）。

哈夫曼编码

• 约定左分支为 0、右分支为 1（或相反）
• 每个叶对应一个符号，根到叶的 0/1 序列即编码
• 前缀性质：任一字符编码都不是另一字符编码的前缀 → 解码无歧义，无需分隔符

权越大的符号越靠近根，编码越短，平均码长更优。

实现直觉

• 用优先队列（最小堆）反复取两个最小元合并，见 优先队列 / 堆
• 结点需能保存左右孩子指针与权值；编码阶段再 DFS 生成码表

小结

哈夫曼树用贪心合并得到最小 WPL，并导出最优前缀码。先会手算小例子，再实现「最小堆 + 合并」。

下一篇：并查集。