哈夫曼树

2026 大纲 四（四）1 哈夫曼（Huffman）树和哈夫曼编码 · 本篇独立承载这一整条。

要解决的问题：省位数，还不能有歧义

发一段只含 ${A, B, C, D}$ 的报文，出现次数分别是 $7, 5, 3, 2$ （共 17 个字符）。等长编码每字符 2 位、总长 34 位；如果让出现次数多的字符用短码（ $A$ 用 1 位、 $B$ 用 2 位、 $C$ 与 $D$ 各 3 位），总长降到 $7 \times 1 + 5 \times 2 + 3 \times 3 + 2 \times 3 = 32$ 位。字符种类越多、频率越不均匀，省得越多。

但不等长编码马上带来新麻烦。0、01、010 这样的编码集合，收到 010 时分不清是 0+10、01+0 还是 010——译码有歧义。

两件事合起来就是这一节要解决的问题：在译码无歧义的前提下，让总编码长度最短。 后面会看到，第一件事的答案是"字符只挂在叶结点上"，第二件事的答案是"WPL 最小的二叉树"。

WPL：只数叶子，只数边

先把度量定死。树的带权路径长度（WPL） 是树中所有叶结点的带权路径长度之和：

W P L = \sum_{k = 1}^{n} w_{k} l_{k}

其中 $w_{k}$ 是第 $k$ 个叶结点的权、 $l_{k}$ 是它到根的路径长度。两条边界要钉死：

只统计叶结点，内部结点带权也不计入；
$l_{k}$ 数的是边，不是点，根到自身是 0 不是 1。这与二叉排序树的 ASL（数结点数）不同，混用会让答案整体偏差一个 $\sum w_{k}$ 。

哈夫曼树的定义就建立在这个量上：给定 $n$ 个权值，构造一棵含 $n$ 个叶结点、每个叶结点权为 $w_{i}$ 的二叉树，WPL 最小的那棵称为最优二叉树或哈夫曼树。

同一组权值能构造出很多棵二叉树，WPL 差别很大。以 ${7, 5, 2, 4}$ 为例：

    (a) 完全二叉树         (b) 单支为主             (c) 哈夫曼树
         ●                      ●                       ●
        / \                    / \                     / \
       ●   ●                  ●   c(2)              a(7)  ●
      / \ / \                / \                        / \
   a(7)b(5)c(2)d(4)        ●   d(4)                  b(5)  ●
                          / \                             / \
                       a(7) b(5)                       c(2) d(4)

WPL = 7×2+5×2+2×2+4×2   WPL = 7×3+5×3+2×1+4×2      WPL = 7×1+5×2+2×3+4×3
    = 36                     = 46                       = 35

叶结点集合完全相同，WPL 分别是 36、46、35。(c) 就是哈夫曼树——权值最大的 $a (7)$ 离根最近，权值最小的 $c (2)$ 、 $d (4)$ 离根最远。

"权大的离根近"为什么最优，一步交换论证就够：设树中两个叶结点 $u, v$ 满足 $w_{u} > w_{v}$ 但 $l_{u} > l_{v}$ （大权反而更深）。交换它们的位置，WPL 变化量

Δ = (w_{u} l_{v} + w_{v} l_{u}) - (w_{u} l_{u} + w_{v} l_{v}) = (w_{u} - w_{v}) (l_{v} - l_{u}) < 0

WPL 严格变小。所以最优树里不可能出现"权大的比权小的更深"。 这一步就是下面那个贪心策略的根据：既然权最小的两个必须最深，那就先把它们配成一对放到最深处。

先看一眼

加载可视化中...

构造：每次合并根权最小的两棵树

把 $n$ 个权值各自作为一棵只有根结点的二叉树，构成森林 $F$ ；
在 $F$ 中选取根权值最小的两棵树作为左右子树，合并为一棵新树，新根权值 $=$ 两者之和；
从 $F$ 中删除被选中的两棵，把新树加入 $F$ ；
重复 ②③，直到 $F$ 中只剩一棵。

每合并一次森林里就少一棵树，从 $n$ 棵减到 1 棵需要恰好 $n - 1$ 次合并。

以 ${2, 3, 5, 7}$ 为例：

初始森林： 2   3   5   7

第 1 步：最小的两个是 2 和 3，合并为 5(新)
        5*
       / \
      2   3            森林： 5*  5   7

第 2 步：最小的两个是 5*(新) 和 5(原)，合并为 10
        10
       /  \
      5*   5           森林： 10  7
     / \
    2   3

第 3 步：剩下 10 和 7，合并为 17
          17
         /  \
       10    7
      /  \
     5*   5
    / \
   2   3

手算时最容易漏的一步，是把新生成的结点放回森林重新参与比较——第 2 步里新生成的 5 就参与了竞争，而且赢了。忘记放回去，后面全错。

WPL 验算： $7 \times 1 + 5 \times 2 + 3 \times 3 + 2 \times 3 = 32$

三条形态性质

性质 1：哈夫曼树中没有度为 1 的结点。 从算法直接看得出来——每次合并必定同时取两棵树作为左右子树，生成的每个内部结点都恰有两个孩子。也可以反证：假设最优树中某结点 $u$ 只有一个孩子子树 $C$ ，把 $u$ 删掉、让 $C$ 直接挂到 $u$ 的双亲， $C$ 中每个叶结点的路径长度都减少 1，其他叶结点不受影响，故 $Δ W P L = - \sum_{k \in C} w_{k} < 0$ ，与"原树最优"矛盾。

性质 2： $n$ 个叶结点的哈夫曼树共有 $2 n - 1$ 个结点。 两条推导互相印证：由性质 1 得 $n_{1} = 0$ ，再由二叉树性质 3 的 $n_{0} = n_{2} + 1$ 得 $n_{总} = n_{0} + n_{2} = 2 n_{0} - 1$ ；或者直接数——初始 $n$ 个叶结点， $n - 1$ 次合并各新增 1 个内部结点，共 $2 n - 1$ 。反过来用同样成立：题目给出总结点数问字符个数，除以 2 再取整即可。

性质 3：哈夫曼树不唯一，但 WPL 唯一。 不唯一有两个来源——左右子树可以交换（不改变任何叶结点的深度）；权值并列最小时选哪两棵都合法。

举个把两点都体现出来的例子：权值 ${1, 2, 3, 3}$ 。第 1 步合并 1 和 2 得到新结点 3，森林变成 ${3^{新}, 3, 3}$ ——三个 3 并列最小。

选法 A：合并 $3^{新}$ 与一个原始 3 得 6，再与剩下的 3 合并。 $W P L = 3 \times 1 + 3 \times 2 + 1 \times 3 + 2 \times 3 = 18$
选法 B：合并两个原始 3 得 6，再与 $3^{新}$ 合并。 $W P L = 3 \times 2 + 3 \times 2 + 1 \times 2 + 2 \times 2 = 18$

两棵树形态不同，连"权值为 1 的字符编码有多长"都不同（A 里 3 位、B 里 2 位），但 WPL 都是 18。

由此得到一条判定方法：给出几棵二叉树问"哪些是这组权值的哈夫曼树"，逐棵算 WPL、等于最小值的就是——不要凭形态判断，更不要以为哈夫曼树只有一棵。

还有两条容易被想当然的边界：

哈夫曼树不一定是完全二叉树。 合并顺序完全由权值决定、与位置无关，不保证每层从左到右填满。权值 ${1, 2, 4, 8}$ 建出的树最后一层只有最左边两个叶子，右边的 8 单独挂在根的右孩子上，显然不完全。
最长编码至多 $n - 1$ 位。 每次合并至多让一条路径加深 1，共 $n - 1$ 次。取到这个上界要求权值增长足够快（如 $1, 1, 2, 3, 5, \dots$ 这种斐波那契式的，每一步合并出的新结点都恰好成为下一步的最小之一）。

WPL 的快算式：所有非叶结点权值之和

W P L = \sum_{叶结点} (权 \times 到根的边数) = \sum_{非叶结点} (该结点的权值)

后一个等式在手算时快得多：构造过程中每次合并产生的那个和，全部加起来就是 WPL——边构造边累加，构造完 WPL 也就出来了，根本不用回头量每片叶子的深度。上面 ${2, 3, 5, 7}$ 的例子里非叶结点权值是 $17, 10, 5$ ，和 $= 32$ ✓

证明也只要一句：每个内部结点的权值 $=$ 它子树内所有叶结点权值之和（构造过程直接保证）。把所有内部结点的权值加起来，等价于每个叶结点的权被它的每一个内部祖先各统计了一次；而一个叶结点的内部祖先个数恰好等于它到根的边数 $l_{k}$ 。

哈夫曼编码与前缀编码

从根到叶结点的路径上，走左分支记 0、走右分支记 1（反过来也行，但全树必须一致），路径上的 0/1 序列就是该字符的编码。用 ${2, 3, 5, 7}$ 那棵树（ $A$ 挂在右边）：

字符	权值	编码	编码长度
A	7	`1`	1
B	5	`01`	2
C	3	`001`	3
D	2	`000`	3

前缀编码：一个编码方案中，任何一个编码都不是其他任何编码的前缀。 ${0, 10, 110, 111}$ 是前缀编码； ${0, 01, 010, 111}$ 不是（0 是 01 的前缀）。

哈夫曼编码一定是前缀编码，理由只有一条：字符只挂在叶结点上。 若编码 $A$ 是编码 $B$ 的前缀，那么路径 $A$ 是路径 $B$ 的最左部分，即 $B$ 经过了 $A$ 的终点——这说明 $A$ 的终点不是叶结点。矛盾。

这条证明反过来就是判定任何编码方案是否为前缀编码的通用办法：把编码画成二叉树（0 走左、1 走右），看字符是否全部落在叶结点上。有字符落在内部结点，它的编码必然是子孙编码的前缀。

译码就是沿树走：从根出发，遇 0 走左、遇 1 走右，一旦到达叶结点就输出该字符并回到根。前缀性保证走到某个叶结点时不可能存在"再多读几位会得到另一个合法字符"的情况，所以每一步的切分唯一确定。用上表译 1001000：读 1 到叶 A，输出 A 回根；读 001 到叶 C，输出 C 回根；读 000 到叶 D，输出 D。结果 ACD。

哈夫曼编码还是最优前缀编码：设字符 $i$ 出现 $w_{i}$ 次、编码长 $l_{i}$ 位，文件总长 $= \sum w_{i} l_{i}$ ；把编码方案画成二叉树后 $l_{i}$ 恰是叶结点到根的路径长度，于是文件总长就是这棵树的 WPL。"设计总长最短的二进制前缀编码"与"以频率为权构造 WPL 最小的二叉树"是同一个问题。

"最优"不等于"唯一"：由性质 3，最优编码方案可以有多套，它们的总长相同。判断一套编码是不是最优，同样要算总长，不能对编码表。

顺带一条对照：定长编码对应的二叉树，所有字符都在同一层（叶层），与频次完全无关。这是定长编码树与哈夫曼编码树最稳的一处区别——后者只有在频次相等或接近时才可能等高。

推广： $k$ 叉哈夫曼树要先补虚结点

题目偶尔会问三叉、四叉的最小带权路径长度。思路照搬——每次取权值最小的 $k$ 棵合并——但有一个必须先做的准备动作。

$k$ 叉合并每次消去 $k$ 个结点、新增 1 个，净减 $k - 1$ 。要从 $n$ 个叶子合并到只剩 1 个根，需要 $\frac{n - 1}{k - 1}$ 次合并。若 $(n - 1) mod (k - 1) \neq 0$ ，最后一轮凑不出 $k$ 个结点——此时要在叶子集合里添加权值为 0 的虚结点，直到 $(n - 1)$ 能被 $(k - 1)$ 整除。

虚结点权值为 0，对 WPL 没有贡献，但它占掉了最深处的一个位置，从而把真实的小权叶子往上抬了——这正是补虚结点能得到更小 WPL 的原因。

例：6 个叶子权 ${2, 3, 4, 5, 6, 7}$ 建三叉哈夫曼树。 $(6 - 1) / (3 - 1) = 2.5$ 不整除，补 1 个权 0 的虚结点，权值集合变成 ${0, 2, 3, 4, 5, 6, 7}$ 。第 1 轮取 ${0, 2, 3}$ 合并得 5；第 2 轮取 ${4, 5, 5}$ 合并得 14；第 3 轮取 ${6, 7, 14}$ 合并得根 27。各叶深度：6、7 为 1，4、5 为 2，2、3 为 3，故

W P L = 6 \times 1 + 7 \times 1 + 4 \times 2 + 5 \times 2 + 2 \times 3 + 3 \times 3 = 46

不补虚结点直接凑，算出来的一定不是最小值。

构造算法的数组实现与复杂度（做代码题、或想弄清复杂度时展开）

由性质 2， $n$ 个叶结点的哈夫曼树共 $2 n - 1$ 个结点，可以存放在一个大小为 $2 n - 1$ 的一维数组里：前 $n$ 个位置放叶结点，后 $n - 1$ 个放合并出的内部结点。

typedef struct {
    int weight;       // 权值
    int parent;       // 双亲下标，-1 表示尚未被合并（即仍是森林中的一棵树根）
    int lchild;       // 左孩子下标
    int rchild;       // 右孩子下标
} HTNode;

void CreateHuffmanTree(HTNode ht[], int w[], int n) {
    int total = 2 * n - 1;                    // 总结点数（性质 2）
    for (int i = 0; i < total; i++) {         // 初始化
        ht[i].parent = ht[i].lchild = ht[i].rchild = -1;
        ht[i].weight = (i < n) ? w[i] : 0;    // 前 n 个是叶结点
    }
    for (int i = n; i < total; i++) {         // 恰好进行 n-1 次合并
        int min1 = -1, min2 = -1;
        for (int j = 0; j < i; j++) {         // 在 parent == -1 的结点中选最小的两个
            if (ht[j].parent != -1) continue; // 已被合并，不再参与
            if (min1 == -1 || ht[j].weight < ht[min1].weight) {
                min2 = min1;
                min1 = j;
            } else if (min2 == -1 || ht[j].weight < ht[min2].weight) {
                min2 = j;
            }
        }
        ht[i].weight = ht[min1].weight + ht[min2].weight;
        ht[i].lchild = min1;
        ht[i].rchild = min2;
        ht[min1].parent = ht[min2].parent = i;    // 标记为"已被合并"
    }
}

parent == -1 充当"仍在森林中"的标志，免去真的维护一个森林集合；合并时把两棵树的 parent 一置，它们自动退出后续竞争。

求编码时反着走：从每个叶结点出发沿 parent 回溯到根，回溯时判断"自己是双亲的左孩子还是右孩子"来生成 0 或 1。由于是从叶往根走，得到的编码是逆序的，需要从后往前填入字符数组。

操作	时间复杂度	来历
构造（线性选最小）	$O (n^{2})$	$n - 1$ 轮合并，每轮线性扫描找最小的两个
构造（用最小堆）	$O (n \log n)$	建堆 $O (n)$ ；每轮两次删最小 + 一次插入
生成全部编码	$O (\sum l_{k})$	每个叶结点回溯到根
译码 $L$ 位编码串	$O (L)$	每读一位在树上走一步

算法里唯一的非常数开销是"选权值最小的两棵树"，这正是优先队列的看家操作——用最小堆把它从 $O (n)$ 降到 $O (\log n)$ 。

考点速记

三条会被反复调用的结论：

WPL 只统计叶结点、路径长度数边；快算式"WPL $=$ 所有非叶结点权值之和"是手算最短路径。
构造是贪心：每次合并根权最小的两棵树，新树必须放回森林，共 $n - 1$ 次合并；因此无度为 1 的结点、 $n$ 个叶子共 $2 n - 1$ 个结点。
哈夫曼树不唯一、单个字符的编码长度也可能不唯一，但 WPL 唯一——判定某棵树是不是哈夫曼树、某套编码是不是最优，一律回到算 WPL / 总长。

这一节在真题里被考过的形式（下方「真题练习」逐题对应）。这是整章出题最密的一节，六类：

求 WPL 或加权平均长度。 给一组频次，建出哈夫曼树再算。用快算式：把每次合并产生的和累加即可。问"加权平均长度"就是 WPL 除以频次总和。
建完树之后数叶子的深度。 变体很多——"编码长度不小于 3 的字符有几个""与某个权值处于相同深度的结点是哪些"。做法都是老老实实把树建完再数深度，没有捷径；建的时候把每一轮的森林状态写下来，别跳步。
判断编码是否为前缀编码 / 是否可能是哈夫曼编码。 前者把编码画成二叉树看字符是否全在叶结点；后者除了前缀性还要核对编码长度与频次的对应关系（频次大的编码不能更长）。
由结点数反求字符数。 用 $2 n - 1$ 。给 115 个结点， $n = 58$ 。
给根到叶的权值序列，判断能否属于同一棵哈夫曼树。 不必建完整的树，只校验局部约束：每个内部结点的权值 $=$ 两个孩子之和，所以"父 $-$ 子 $=$ 另一个子"必须为正；两条路径推出同一结点的另一孩子时结果必须一致。出现 $\leq 0$ 或推导冲突就排除。
关于哈夫曼树 / 编码的判断题。 三条被反复设为选项的结论：哈夫曼树不一定是完全二叉树；定长编码树的所有字符都在同一层；哈夫曼树中没有度为 1 的结点。

另有两道大题也建立在这一节上：

$N$ 个不等长有序表的最优合并策略。 "每次挑最短的两个表先合并"就是哈夫曼贪心，合并的总比较次数对应 WPL。答题时要把"为什么先合并短的"讲出来——短表参与的合并轮次多，让它们的元素被反复扫描的代价最小。
前缀编码的判定与译码。 问"用什么数据结构保存不等长前缀编码"，答二叉树（编码树），字符全在叶结点；译码就是沿树走到叶输出后回根；判定前缀特性就是逐个编码在树上走一遍，中途撞到已有字符（说明它是别人的前缀）或走完停在内部结点（说明别人是它的前缀）都判否。

易错：手算时忘了把新生成的结点放回森林。 这是构造题失分的主要来源。

易错：WPL 把内部结点的权也算进去，或把路径长度数成结点数。 只数叶子、只数边。

易错：认为哈夫曼树唯一、或认为它一定是完全二叉树。 都不成立，唯一的是 WPL。

易错： $k$ 叉哈夫曼树不补权 0 的虚结点。 $(n - 1)$ 不能被 $(k - 1)$ 整除时必须补，否则算出的不是最小值。

教材出处

路径、路径长度、树的路径长度、权、结点的带权路径长度、树的带权路径长度 $W P L = \sum w_{k} l_{k}$ 六个术语的定义，以及哈夫曼树（最优二叉树）的定义"其中带权路径长度 WPL 最小的二叉树称做最优二叉树或哈夫曼树"：严蔚敏《数据结构（C 语言版）》（第 2 版）印刷 p136（5.7.1 节）
以 4 个叶结点 $a, b, c, d$ 带权 $7, 5, 2, 4$ 的三棵二叉树为例给出 $W P L = 36 / 46 / 35$ 的对照，以及"在哈夫曼树中，权值越大的结点离根结点越近"：印刷 p137
哈夫曼树的构造过程（四步）：印刷 p137（5.7.2 节）
"由于哈夫曼树中没有度为 1 的结点，则一棵有 $n$ 个叶子结点的哈夫曼树共有 $2 n - 1$ 个结点，可以存储在一个大小为 $2 n - 1$ 的一维数组中"，以及哈夫曼树结点的存储结构与构造算法 5.10（"通过 $n - 1$ 次的选择、删除与合并来创建哈夫曼树"）：印刷 p138
前缀编码的定义（"任一个编码都不是其他任何编码的前缀（最左子串）……前缀编码可以保证对压缩文件进行解码时不产生二义性"）、哈夫曼编码的定义（左分支赋 0、右分支赋 1），性质 1「哈夫曼编码是前缀编码」的完整证明（"若路径 A 是另一条路径 B 的最左部分，则 B 经过了 A，则 A 的终点一定不是叶子；而哈夫曼编码对应路径的终点一定为叶子"）与性质 2「哈夫曼编码是最优前缀编码」的证明（文件总长 $\sum w_{i} l_{i}$ 恰为二叉树的带权路径长度）：印刷 p140（5.7.3 节）
求哈夫曼编码的实现思路"依次以叶子为出发点，向上回溯至根结点为止；回溯时走左分支则生成代码 0，走右分支则生成代码 1"，以及"得到的编码顺序是从右向左的，故将编码向数组 cd 存放的顺序也是从后向前"：印刷 p140–p141

说明： $k$ 叉哈夫曼树与补虚结点的做法不在上述教材范围内，本篇依据"每次合并净减 $k - 1$ 个结点"这一事实自行推出，故不标页码。

真题练习

2026Q52分 2025Q52分 2023Q42分 2022Q52分 2021Q52分 2020Q4210分 2019Q32分 2018Q52分 2017Q62分 2015Q32分 2014Q62分 2013Q42分 2012Q4110分 2010Q62分

哈夫曼树

要解决的问题：省位数，还不能有歧义

WPL：只数叶子，只数边

先看一眼

构造：每次合并根权最小的两棵树

三条形态性质

WPL 的快算式：所有非叶结点权值之和

哈夫曼编码与前缀编码

推广： $k$ 叉哈夫曼树要先补虚结点

考点速记

相关知识

相关文章

交互体验

真题练习

相关真题（14题）

哈夫曼树 ​

要解决的问题：省位数，还不能有歧义 ​

WPL：只数叶子，只数边 ​

先看一眼 ​

构造：每次合并根权最小的两棵树 ​

三条形态性质 ​

WPL 的快算式：所有非叶结点权值之和 ​

哈夫曼编码与前缀编码 ​

推广：k 叉哈夫曼树要先补虚结点 ​

考点速记 ​

相关知识 ​

相关文章

交互体验

真题练习 ​

相关真题（14题）

哈夫曼树

要解决的问题：省位数，还不能有歧义

WPL：只数叶子，只数边

先看一眼

构造：每次合并根权最小的两棵树

三条形态性质

WPL 的快算式：所有非叶结点权值之和

哈夫曼编码与前缀编码

推广： $k$ 叉哈夫曼树要先补虚结点

考点速记

相关知识

真题练习