哈夫曼树和哈夫曼编码

结点的权：赋予结点的有意义的数值。带权路径长度（WPL）：从根到该结点的路径长度 $\times$ 结点权值。树的 WPL = 所有叶子带权路径之和：

$$WPL = \sum_{i=1}^{n} w_i l_i$$

哈夫曼树（最优二叉树）：在含 n 个带权叶子的二叉树中 WPL 最小者。特点：

• 没有度为 1 的结点（$n_1 = 0$）；
• n 个叶子 → 共 2n−1 个结点（$n_0=n$，$n_2=n-1$）；
• 哈夫曼树不唯一，但 WPL 唯一。

哈夫曼算法（贪心）

1. n 个结点作 n 棵只含根结点的树，构成森林 F；
2. 在 F 中选两棵权值最小的树，作为新结点的左右子树，新结点权值 = 二者之和；
3. 从 F 中删除这两棵树，把新树加入 F；
4. 重复 2、3 直到只剩一棵树。

编解码

编码：字符 → 对应哈夫曼编码（如 "FACE" → "11 1000 101 01"）。解码：从根开始读 0 走左、读 1 走右，到叶子输出字符（如 "11100010101" → F A C E）。