数据结构第 5 章：树与二叉树

408 数据结构「树与二叉树」复习：核心知识点、真题题型、通用解法与易错点。

本章对照站内两套资料整理：408 模拟选择题的“第 5 章”就是《树与二叉树》；408 真题库由于没有把“串”单列，所以同一内容编号为“第 4 章树与二叉树”。站内真题又按“树基本概念、二叉树基础、遍历、线索二叉树、树与森林、树与二叉树应用”组织，非常适合按题型总结。(Any Docs)

建议把这一章理解成下面 6 条主线：

结点数量关系 → 完全二叉树 → 遍历 → 线索化 → 树/森林转换 → 哈夫曼树

其中从站内真题密度和综合程度来看，遍历、哈夫曼、树森林转换尤其重要；算法大题也主要从“遍历框架”往外扩展，例如表达式树、求 WPL、前缀编码树。(Any Docs)

一、树的基本概念与数量关系

这是整个第 5 章最重要的“算数基础”。

1. 树最核心的等式：边数 = 结点数 − 1

只要是一棵非空树：

E = n - 1

其中：

$n$ ：结点数；
$E$ ：边数。

假设度为 $i$ 的结点有 $n_{i}$ 个，因为“树中结点的度”表示孩子数，所以边数还可以写成

E = i \geq 1 \sum i n_{i}

因此：

n - 1 = i \geq 1 \sum i n_{i}

而

n = i \geq 0 \sum n_{i}

两式结合，是几乎所有“求叶结点数”问题的来源。

整理得：

n_{0} = 1 + i \geq 2 \sum (i - 1) n_{i}

注意：

$n_{1}$ 消失了。

所以以后看到：

给出各个度数结点的数量，求叶结点数

直接想到这个公式。

题型 1：根据各度结点数求叶结点数

408 真题 2010

题目大意：

一棵度为 4 的树中，有 20 个度为 4 的结点， 10 个度为 3 的结点， 1 个度为 2 的结点， 10 个度为 1 的结点，问叶结点有多少？

选项中答案为 82。(Any Docs)

直接使用：

n_{0} = 1 + (2 - 1) n_{2} + (3 - 1) n_{3} + (4 - 1) n_{4}

代入：

n_{0} = 1 + 1 + 2 \times 10 + 3 \times 20

= 82

所以答案：

82

这题真正应该记什么？

不是记 82，而是看到：

$n_{2}, n_{3}, n_{4}, \dots$

立即写：

n_{0} = 1 + i \geq 2 \sum (i - 1) n_{i}

而且：

度为 1 的结点数量对叶结点公式没有直接影响。

这是很容易出干扰项的地方。

二、 $k$ 叉树、正则 $k$ 叉树

普通 $k$ 叉树只是：

每个结点最多有 $k$ 个孩子。

而正则 $k$ 叉树：

每个非叶结点恰好有 $k$ 个孩子。

这两个概念一定不要混。

1. 高度为 $h$ 的 $k$ 叉树最多多少结点？

每层完全填满：

1, k, k^{2}, \dots, k^{h - 1}

所以：

n_{m a x} = 1 + k + \dots + k^{h - 1}

即

n_{m a x} = \frac{k ^{h} - 1}{k - 1}

题型 2：给结点数求最小高度

408 真题 2022

题目：

三叉树 $T$ 有 244 个结点，叶结点高度为 1，问 $T$ 的高度至少是多少？

(Any Docs)

要让高度尽可能小，就要让每一层都尽量装满。

三叉树高度 $h$ 最多：

\frac{3 ^{h} - 1}{2}

检查 $h = 5$ ：

\frac{3 ^{5} - 1}{2} = 121

装不下 244 个。

检查 $h = 6$ ：

\frac{3 ^{6} - 1}{2} = 364

可以。

因此：

h_{m i n} = 6

通用套路

“给总结点数，问高度至少多少”：

求最小的 $h$ ，满足

n \leq \frac{k ^{h} - 1}{k - 1}

三、正则 $k$ 叉树：非常值得掌握

408 真题 2016

题目：

非空正则 $k$ 叉树中，每个非叶结点都有 $k$ 个孩子。

若有 $m$ 个非叶结点，叶结点有多少？

若高度为 $h$ ，总结点数最多和最少分别是多少？

(Any Docs)

这是这一章非常好的综合公式题。

1. 叶结点数

设叶结点数为 $n_{0}$ 。

总结点：

n = m + n_{0}

因为每个非叶结点有 $k$ 个孩子：

E = k m

又因为树有：

E = n - 1

所以：

k m = m + n_{0} - 1

于是：

n_{0} = (k - 1) m + 1

二叉树情况下 $k = 2$ ：

n_{0} = m + 1

这就是后面著名的：

n_{0} = n_{2} + 1

2. 高度 $h$ 时最多结点

全部填满：

n_{m a x} = \frac{k ^{h} - 1}{k - 1}

3. 高度 $h$ 时最少结点

正则 $k$ 叉树不能像普通树一样“一根链”。

因为一个结点要么：

没孩子；
要么必须有 $k$ 个孩子。

为了高度达到 $h$ ，只让每层一个结点继续向下成为非叶结点。

于是共有 $h - 1$ 个非叶结点。

所以：

n_{m i n} = k (h - 1) + 1

即：

n_{m i n} = k (h - 1) + 1

这个“最少”很容易出错。

四、二叉树的三大计数公式

设：

$n_{0}$ ：度为 0 的结点；
$n_{1}$ ：度为 1 的结点；
$n_{2}$ ：度为 2 的结点。

总数：

n = n_{0} + n_{1} + n_{2}

边数：

n - 1 = n_{1} + 2 n_{2}

两式相减：

n_{0} + n_{1} + n_{2} - 1 = n_{1} + 2 n_{2}

得到最重要公式：

n_{0} = n_{2} + 1

它和 $n_{1}$ 无关。

五、二叉链表的空指针数

一个结点有两个孩子指针。

所以总指针数：

2 n

树中的真实边数：

n - 1

每条真实边占一个非空指针。

所以非空指针：

n - 1

空指针：

2 n - (n - 1)

因此：

n + 1

这也是为什么线索二叉树有足足 $n + 1$ 个空指针可以利用。

六、满二叉树、完全二叉树、正则二叉树一定分清

满二叉树

每一层都完全填满。

高度为 $h$ ：

n = 2^{h} - 1

叶结点：

n_{0} = 2^{h - 1}

完全二叉树

除了最后一层外全部填满，最后一层结点连续靠左。

它不要求所有非叶结点都有两个孩子。

倒数第二层可以出现：

只有左孩子，没有右孩子

的结点。

正则二叉树 / 严格二叉树

每个结点度只能是：

0 或 2

因此：

n_{1} = 0

模拟题也专门考过：

$n$ 个结点的正则二叉树有多少叶结点？

利用

n_{0} = n_{2} + 1

以及

n = n_{0} + n_{2}

得到：

n_{0} = \frac{n + 1}{2}

(Any Docs)

七、完全二叉树——408 必考公式群

如果顺序编号从 1 开始：

对于编号 $i$ ：

父结点：

⌊ \frac{i}{2} ⌋

左孩子：

2 i

右孩子：

2 i + 1

当然必须保证编号不超过 $n$ 。

叶结点编号范围

编号：

⌊ \frac{n}{2} ⌋ + 1, \dots, n

全部是叶结点。

所以叶结点数量：

n - ⌊ \frac{n}{2} ⌋

即：

⌈ \frac{n}{2} ⌉

408 真题 2011

题目：

一棵完全二叉树有 768 个结点，叶结点有多少？

(Any Docs)

直接：

n_{0} = ⌈ \frac{768}{2} ⌉ = 384

所以：

384

八、完全二叉树的高度

含 $n$ 个结点：

h = ⌊ lo g_{2} n ⌋ + 1

等价地：

h = ⌈ lo g_{2} (n + 1)⌉

九、题型：某层叶结点 + 最大总结点数

408 真题 2009

题目：

一棵完全二叉树，第 6 层有 8 个叶结点，问总结点数最多多少？

(Any Docs)

第 6 层最多：

2^{5} = 32

个结点。

其中 8 个已经是叶结点，因此最多：

32 - 8 = 24

个第 6 层结点还能继续拥有孩子。

所以第 7 层最多：

24 \times 2 = 48

前 6 层全部填满：

2^{6} - 1 = 63

所以：

n_{m a x} = 63 + 48 = 111

答案：

111

这类题核心

看到：

某层有 $x$ 个叶结点，问最大结点数

就要想：

剩下的非叶结点全部生两个孩子。

十、顺序存储的“坑”：不是有多少结点就开多少空间

408 真题 2020

题目：

对任意高度为 5、有 10 个结点的二叉树，采用顺序存储，每个结点 1 个单元，至少准备多少存储单元？

(Any Docs)

关键词：

任意二叉树

不是完全二叉树。

最坏情况下，第 5 层可能出现最右端结点。

顺序编号最右端：

2^{5} - 1 = 31

所以数组至少需要：

31

而不是 10。

这说明：

顺序存储最适合完全二叉树。

对于斜树可能极其浪费空间。

十一、完全二叉树共同祖先问题

模拟题：

完全二叉树用 $A [1 \dots N]$ 存储，9 号和 11 号结点共同祖先是谁？

沿父节点不断：

i \leftarrow ⌊ \frac{i}{2} ⌋

9：

9 \to 4 \to 2 \to 1

11：

11 \to 5 \to 2 \to 1

十二、二叉树遍历：这一章第一大核心

四种遍历必须形成条件反射。

先序

根 \to 左 \to 右

即 NLR。

中序

左 \to 根 \to 右

即 LNR。

后序

左 \to 右 \to 根

即 LRN。

层序

一层一层，从左到右。

用队列。

十三、不要死背 NLR：考试可能故意换顺序

408 真题 2009

题目给一棵二叉树，并规定：

$N$ ：根；
$L$ ：左子树；
$R$ ：右子树。

得到序列：

3, 1, 7, 5, 6, 2, 4

问采用什么遍历方式。

答案是：

R N L

也就是：

右子树 → 根 → 左子树

(Any Docs)

所以不要以为遍历只会考三种标准顺序。

它完全可以考：

N R L, R N L, R L N

方法都一样：

递归定义是什么，就严格按递归定义走。

十四、已知遍历序列重建二叉树

这是本章最重要的能力之一。

结论 1：先序 + 中序

当结点值互不相同时，可以唯一确定。

因为：

先序第一个 = 根。

然后在中序中找到根：

[左子树] 根 [右子树]

递归即可。

结论 2：后序 + 中序

也能唯一确定。

因为：

后序最后一个 = 根。

结论 3：先序 + 后序

一般：

不能唯一确定

原因是无法判断单孩子究竟是左孩子还是右孩子。

十五、非常经典的“先序与后序互逆”

408 真题 2011

题目：

先序：

1, 2, 3, 4

后序：

4, 3, 2, 1

问哪个中序序列不可能出现。(Any Docs)

这个信息说明什么？

先序：

根首先出现。

后序：

根最后出现。

现在二者完全反过来：

1, 2, 3, 4

与：

4, 3, 2, 1

说明每个结点只有一个孩子。

结构是一条链：

1
|
2
|
3
|
4

但每条边都可以是：

左孩子；
或右孩子。

所以树并不唯一。

这类题最重要的结论：

先序序列与后序序列完全逆序，往往意味着二叉树是一棵单支树。

十六、遍历序列相同的特殊树——非常爱考

前序 = 中序

前序：

根 \to 左 \to 右

中序：

左 \to 根 \to 右

要完全一样，就不能出现左子树。

因此：

所有结点均无左孩子

也就是一条不断向右发展的树。

模拟题也明确考过：

前序和中序相同，应为只有根结点，或所有结点只有右子树。

(Any Docs)

中序 = 后序

同理：

中序：

左 \to 根 \to 右

后序：

左 \to 右 \to 根

要相同，就不能有右子树。

所以：

所有结点均无右孩子

前序 = 后序

非空树中通常只有：

一个结点

才能完全相同。

前序与后序互逆

则可以是一条单支树。

这一组结论很适合直接出选择题。

十七、中序相邻关系——近年非常重要

这类题已经连续出现高质量真题。

408 真题 2022

题目：

$p, q$ 在二叉树中序序列中相邻，并且 $p$ 在 $q$ 前面。下列关系中哪一个不可能？

I. $q$ 是 $p$ 的父结点 II. $q$ 是 $p$ 的右孩子 III. $q$ 是 $p$ 的右兄弟 IV. $q$ 是 $p$ 的祖父

答案只有 III 不可能。(Any Docs)

为什么兄弟不可能？

假设：

    x
   / \
  p   q

中序遍历必然：

p 子树 \to x \to q 子树

父结点 $x$ 一定夹在二者之间。

所以兄弟不可能相邻。

十八、2024 真题：中序前驱和后继的结构

题目：

$v$ 有两个孩子，并且中序序列局部为
$\dots, p, v, q, \dots$
判断 $p, q$ 的孩子情况。

答案：

p 无右孩子, q 无左孩子

(Any Docs)

为什么？

$p$ 是 $v$ 左子树中最后访问的结点。

因此 $p$ 是：

左子树最右边的结点。

如果 $p$ 有右孩子，就应该继续遍历右子树，不可能马上到 $v$ 。

所以：

p 无右孩子

同理：

$q$ 是 $v$ 右子树最先访问的结点，所以它必须是右子树最左边结点：

q 无左孩子

强烈建议记：

某结点 $x$ 有左、右子树时：

中序前驱 = 左子树最右结点

中序后继 = 右子树最左结点

这又直接通向后面的线索二叉树和二叉排序树。

十九、叶结点在三种深度优先遍历中的相对顺序

一个很容易被忽视，但模拟题很有价值的结论：

对同一棵二叉树，叶结点在先序、中序、后序中的相对先后顺序不会改变。

原因是三种遍历都始终遵守：

左子树整体在右子树之前。

变化的只是根什么时候访问。

所以叶结点从左到右的相对顺序保持一致。

二十、遍历算法：大题不能只会手算

标准二叉链表：

typedef struct BiTNode {
    ElemType data;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

先序

void PreOrder(BiTree T) {
    if (T == NULL) return;

    visit(T);
    PreOrder(T->lchild);
    PreOrder(T->rchild);
}

中序

void InOrder(BiTree T) {
    if (T == NULL) return;

    InOrder(T->lchild);
    visit(T);
    InOrder(T->rchild);
}

后序

void PostOrder(BiTree T) {
    if (T == NULL) return;

    PostOrder(T->lchild);
    PostOrder(T->rchild);
    visit(T);
}

时间复杂度全部：

O (n)

递归辅助空间：

O (h)

其中 $h$ 是树高。

最坏斜树：

O (n)

平衡树：

O (lo g n)

二十一、算法题第一万能模板：求高度

模拟题给了：

int maxFunc(TreeNode* root) {
    if (root == NULL) return 0;
    return max(maxFunc(root->left),
               maxFunc(root->right)) + 1;
}

问复杂度。(Any Docs)

虽然递归树看起来有两个递归分支，但每个树结点实际上只访问一次。

所以：

O (n)

不是：

O (2^{n})

也不是平衡树情况下的：

O (lo g n)

$lo g n$ 是递归深度，不是访问结点总数。

这是非常典型的复杂度陷阱。

二十二、删除二叉树为什么必须后序？

模拟题明确考了这一点。(Any Docs)

假设：

free(T);
freeTree(T->left);

那么访问 T->left 时 $T$ 已经被释放，非常危险。

所以必须：

freeTree(T->left);
freeTree(T->right);
free(T);

即：

左 \to 右 \to 根

所以：

删除、释放一棵树天然适合后序遍历。

二十三、表达式树——408 算法大题典型

408 真题 2017

要求：

给定表达式二叉树，输出等价的中缀表达式，并通过括号体现原表达式树的计算次序。

(Any Docs)

最核心观察：

中缀表达式本身对应：

中序遍历

但问题在于：

a + b * c

和

(a + b) * c

中序访问字符可能相似，但运算顺序不同。

因此每个非根运算符子树整体加括号。

核心结构：

void PrintExpression(BiTree T, int depth) {
    if (T == NULL)
        return;

    int op = T->left != NULL || T->right != NULL;

    if (op && depth > 0)
        printf("(");

    PrintExpression(T->left, depth + 1);

    printf("%s", T->data);

    PrintExpression(T->right, depth + 1);

    if (op && depth > 0)
        printf(")");
}

这个大题应该抽象成什么？

不是“背 2017 代码”。

而是：

只要题目要求基于树结构输出表达式，首先想到中序遍历；若树形本身代表优先级，需要在递归进入子表达式时补括号。

二十四、层序遍历

层序不能用普通 DFS 栈。

核心数据结构：

队列

伪代码：

enqueue(Q, root);

while (!empty(Q)) {
    T = dequeue(Q);
    visit(T);

    if (T->left)
        enqueue(Q, T->left);

    if (T->right)
        enqueue(Q, T->right);
}

它又可以衍生：

求树宽；
找某层结点；
判断完全二叉树；
求层数；
按层输出。

二十五、如何判断完全二叉树——预测算法题

这是一个非常有价值的潜在考法。

层序遍历。

一旦遇到第一个空孩子位置：

后面不得再出现非空结点。

例如按层序把指针也入队：

A B C D NULL NULL E

如果已经出现 NULL，后面又出现 E：

\Rightarrow

不是完全二叉树。

时间复杂度：

O (n)

二十六、线索二叉树

二叉链表有：

n + 1

个空指针。

线索化就是利用这些空指针保存：

前驱；
后继。

一般加入：

int ltag;
int rtag;

约定：

l t a g = 0

表示 lchild 是真正左孩子，

l t a g = 1

表示 lchild 是线索。

右边同理。

二十七、中序线索树：最重要

对于结点 $p$ 。

求中序后继

如果右指针是线索：

r t a g = 1

直接：

p - > r c hi l d

如果有真正右孩子：

r t a g = 0

则：

中序后继 = 右子树最左下结点。

求中序前驱

对称：

若：

l t a g = 1

则：

p - > l c hi l d

就是前驱。

否则：

左子树最右下结点。

二十八、408 真题 2014：线索指向谁

题目给一棵二叉树，对它中序线索化，问叶结点 $x$ 的左右线索指向谁。

站内给出的中序序列是：

d, e, b, x, a, c

因此：

x 的前驱 = b

x 的后继 = a

所以：

b, a

(Any Docs)

做线索题最稳方法

不要在图上乱猜。

先写完整遍历序列：

\dots, p, x, q, \dots

那么如果 $x$ 左右孩子指针为空：

左线索 \to p

右线索 \to q

就完了。

二十九、后序线索树的难点

408 真题 2013

题目：

$X$ 是后序线索二叉树中的叶结点，并且 $X$ 有左兄弟 $Y$ ，问 $X$ 的右线索指向谁？

(Any Docs)

因为 $X$ 有左兄弟，所以 $X$ 是父结点的右孩子。

后序：

左 \to 右 \to 根

访问完右子树的 $X$ ，下一步就是父结点。

所以：

X 的后序后继 = X 的父结点

答案就是父结点。

三十、线索树最容易混淆的能力边界

模拟题专门考过：

哪种线索树仍不能方便地求相应后继？

答案：

只有孩子指针的后序线索树，不方便求后序后继。

(Any Docs)

原因在于后序后继经常需要：

向上找双亲。

但普通二叉链表没有 parent 指针。

因此可以记：

线索类型	比较容易
先序线索	找先序后继
中序线索	找前驱、后继
后序线索	找后序前驱

反方向常常需要双亲信息。

三十一、树与二叉树转换：左孩子—右兄弟

这是本章第二个极易混乱区域。

一棵普通树：

A
├── B
├── C
└── D

转换成二叉树：

规则只记一句：

左孩子，右兄弟

也就是：

左指针 → 第一个孩子；
右指针 → 下一个兄弟。

三十二、森林转换成二叉树

例如森林：

T1    T2    T3
A     D     F

转换时，各棵树的根也视为兄弟。

所以：

A
 \
  D
   \
    F

因此：

二叉树根结点的右孩子链，就是森林各棵树的根。

这个结论被 2021 真题直接考了。

三十三、408 真题 2021：求森林有多少棵树

题目：

对应二叉树 $T$ ：

先序：

a, b, d, c, e, g, f

中序：

b, d, a, e, g, c, f

问原森林 $F$ 有几棵树。(Any Docs)

先根据先序 + 中序还原二叉树。

得到根结点的右孩子链：

a \to c \to f

所以森林有：

3

棵树。

通用结论

森林树的棵数 = 对应二叉树根的右孩子链结点数

三十四、原树叶结点对应二叉树什么？

408 真题 2014

题目：

森林 $F$ 转换为二叉树 $T$ ， $F$ 的叶结点数等于 $T$ 中哪种结点数量？

答案：

左孩子指针为空

(Any Docs)

为什么？

原森林中：

叶结点 = 没孩子。

而二叉树：

左指针 = 第一个孩子。

所以：

没有孩子 ⟺ 左孩子为空

这是非常漂亮的结构映射。

三十五、森林的“结点−边−树数”公式

假设森林有：

$N$ 个结点；
$E$ 条边；
$k$ 棵树。

每棵树：

E_{i} = N_{i} - 1

加起来：

E = N - k

所以：

k = N - E

408 真题 2016

题目：

森林有 15 条边、25 个结点，问共有几棵树？

(Any Docs)

直接：

k = 25 - 15

k = 10

这种题基本属于送分题。

三十六、树遍历与对应二叉树遍历的关系

这是必须背下来的两个结论：

普通树的先根遍历：

= 对应二叉树的先序遍历

普通树的后根遍历：

= 对应二叉树的中序遍历

2019 真题就直接考了第二条。(Any Docs)

所以：

树后根 \leftrightarrow 二叉树中序

不要误选二叉树后序。

三十七、408 真题 2020：森林遍历 + 重建二叉树

题目给森林：

先根：

ab c d e f

后根：

ba df ec

问对应二叉树的后序遍历。(Any Docs)

利用转换：

森林先根 = 二叉树先序：

ab c d e f

森林后根 = 二叉树中序：

ba df ec

于是变成：

已知二叉树先序 + 中序，求后序。

重建后得到：

b f e d c a

这个题特别值得掌握，因为它把：

树森林转换 + 遍历重建

两个知识点组合起来了。

以后综合题很可能继续这样命题。

三十八、2011 真题的一个经典转换结论

题目：

一棵树有 2011 个结点、116 个叶结点。转换成二叉树后，无右孩子的结点多少？

(Any Docs)

原树非叶结点：

2011 - 116 = 1895

每个非叶结点的一组孩子里：

最后一个孩子没有右兄弟。

因此产生 1895 个没有右孩子的结点。

此外原树根也没有兄弟：

+ 1

所以：

1895 + 1 = 1896

这是“左孩子右兄弟”理解程度非常好的检验题。

三十九、哈夫曼树——第 5 章最高频模块之一

定义：

给定叶结点权值 $w_{i}$ ，带权路径长度：

W P L = i = 1 \sum n w_{i} l_{i}

其中 $l_{i}$ 是叶结点到根的路径长度。

使：

W P L

最小的二叉树就是哈夫曼树。

四十、哈夫曼树怎么构造？

永远重复：

每次选当前权值最小的两个结点。

合并成新结点：

w = w_{1} + w_{2}

再把新权值放回集合。

一直到只剩一个。

四十一、最重要捷径：WPL = 所有合并权值之和

408 真题 2021

权值：

10, 12, 16, 21, 30

求最小 WPL。(Any Docs)

合并：

10 + 12 = 22

剩：

16, 21, 22, 30

继续：

16 + 21 = 37

然后：

22 + 30 = 52

最后：

37 + 52 = 89

WPL：

22 + 37 + 52 + 89

200

完全不需要真的画树。

强烈建议

凡题目只求 WPL：

不用画树，直接累计每次合并值

四十二、2023 真题：平均编码长度

字符频率：

3, 4, 5, 6, 8, 10

(Any Docs)

依次合并：

3 + 4 = 7

5 + 6 = 11

7 + 8 = 15

10 + 11 = 21

15 + 21 = 36

因此：

W P L = 7 + 11 + 15 + 21 + 36 = 90

总频数：

3 + 4 + 5 + 6 + 8 + 10 = 36

所以平均编码长度：

\overset{ˉ}{L} = \frac{W P L}{\sum _{i} w _{i}}

即：

\overset{ˉ}{L} = \frac{90}{36} = 2.5

答案：

2.5

所以记住：

加权平均码长 = \frac{W P L}{总权值}

四十三、哈夫曼树的结点数量关系

二叉哈夫曼树中：

n_{1} = 0

即没有度为 1 的结点。

所以：

n_{0} = n_{2} + 1

如果有 $n$ 个待编码字符：

字符对应叶结点。

因此：

n_{0} = n

内部结点：

n_{2} = n - 1

总数：

N = n + (n - 1)

所以：

N = 2 n - 1

408 真题 2019

题目：

某哈夫曼树一共有 115 个结点，问对多少个不同符号进行编码？

(Any Docs)

设字符数 $n$ ：

2 n - 1 = 115

所以：

n = 58

答案：

58

另外立刻得到：

二叉哈夫曼树总结点数一定是奇数。

模拟题也专门考了这个性质。(Any Docs)

四十四、哈夫曼树不是完全二叉树

408 真题 2010

题目问：

对互不相同权值构造哈夫曼树，哪个说法错误？

其中：

“哈夫曼树一定是完全二叉树”

是错误的。(Any Docs)

一定满足的是：

不存在度为 1 的结点

但不保证：

完全；
平衡；
满二叉树的层次形式。

所以：

哈夫曼树是正则二叉树，但不一定是完全二叉树

这里“正则”指所有非叶结点度为 2。

四十五、哈夫曼编码为什么是前缀编码？

字符只存放在叶结点。

因此一个字符对应的路径不可能是另一个叶结点路径的前缀。

换句话说：

一个叶结点不可能是另一个叶结点的祖先。

所以哈夫曼编码天然具有：

前缀特性

也就是：

任一字符编码都不是另一个字符编码的前缀。

四十六、408 真题 2014：判断前缀编码

题目给若干组编码，问哪一组不是前缀编码。

其中一组选项含：

110, 1100

因为：

110

是

1100

的前缀。

所以不满足。(Any Docs)

做这种题不要想哈夫曼树。

直接扫描：

有没有短编码完整出现在另一个编码最前面？

四十七、Kraft 不等式——模拟题中的高质量拓展

若二进制前缀码的码长分别为：

l_{1}, l_{2}, \dots, l_{n}

则必须满足：

i = 1 \sum n 2^{- l_{i}} \leq 1

模拟题：

已有编码 0 和 10，所有编码长度不超过 4，最多还能编码几个字符？

(Any Docs)

已有容量：

2^{- 1} + 2^{- 2} = \frac{1}{2} + \frac{1}{4} = \frac{3}{4}

剩余：

\frac{1}{4}

长度 4 的一个码字占：

2^{- 4} = \frac{1}{16}

所以最多：

\frac{1/4}{1/16} = 4

答案：

4

剩余可写成：

这个知识点很适合作为未来新考法。

四十八、多叉哈夫曼树：容易突然出冷题

408 真题 2013

题目：

三叉树有 6 个叶结点，权值为：
$2, 3, 4, 5, 6, 7$
求最小 WPL。

(Any Docs)

很多人会直接每次取 3 个，然后出错。

对于 $k$ 叉哈夫曼树，必须满足：

n_{0} - 1

能被

k - 1

整除。

这里：

6 - 1 = 5

不能被 2 整除。

所以补一个：

0

得到：

0, 2, 3, 4, 5, 6, 7

然后每次取三个最小值：

0 + 2 + 3 = 5

4 + 5 + 5 = 14

6 + 7 + 14 = 27

因此：

W P L = 5 + 14 + 27

46

四十九、 $k$ 叉哈夫曼树补多少虚结点？

叶结点数 $n$ 。

需要满足：

(n^{'} - 1) mod (k - 1) = 0

设补 $d$ 个：

n^{'} = n + d

所以求最小非负 $d$ ，使：

n + d - 1

能被 $k - 1$ 整除。

可以写：

d = ((k - 1) - ((n - 1) mod (k - 1))) mod (k - 1)

虚结点权值：

0

五十、最优合并问题 = 哈夫曼问题

408 真题 2012

有 6 个升序表：

10, 35, 40, 50, 60, 200

个元素。

需要经过 5 次两两合并，要求最坏比较总次数最少。(Any Docs)

两个长度为 $m, n$ 的有序表合并，最坏比较：

m + n - 1

因此应该：

每次合并两个最短的表。

过程：

10 + 35 = 45

40 + 45 = 85

50 + 60 = 110

85 + 110 = 195

195 + 200 = 395

对应比较：

44, 84, 109, 194, 394

总共：

44 + 84 + 109 + 194 + 394 = 825

所以：

825

为什么是哈夫曼？

每个原始表长度就是叶权值。

一个表每被合并一次，就相当于其权值多贡献一次。

所以总合并代价和：

W P L

本质一样。

这叫：

最优合并模式

以后看到：

合并文件；
合并数组；
合并有序表；
合并数据块；
希望总成本最小；

都应该想到哈夫曼思想。

五十一、求任意二叉树 WPL——408 算法大题

408 真题 2014

题目：

二叉树叶结点中保存非负权值，设计求整棵树 WPL 的算法。

(Any Docs)

定义：

W P L = leaf v \sum w e i g h t (v) \times d e pt h (v)

所以只需 DFS。

long long WPL(BiTree T, int depth) {
    if (T == NULL)
        return 0;

    if (T->left == NULL && T->right == NULL)
        return (long long)T->weight * depth;

    return WPL(T->left, depth + 1)
         + WPL(T->right, depth + 1);
}

初始：

WPL(root, 0);

时间：

O (n)

递归空间：

O (h)

五十二、前缀编码 + Trie——2020 大题非常有价值

408 真题 2020

题目大意：

有一个二进制不等长前缀编码集合。

用什么数据结构保存？

如何译码？

如何判断编码集合是否满足前缀特性？

(Any Docs)

答案本质：

二叉 Trie / 编码树

规定：

0 → 左；
1 → 右。

译码

读每一位。

例如：

011010...

从根开始：

0 → 左；
1 → 右。

走到字符叶结点：

输出字符，然后重新回根。

判断是否满足前缀性质

依次插入所有编码。

插入某个编码时有三种非法情况。

情况 1

编码还没读完，就已经遇到字符终止结点。

例如已有：

现在插入：

则 10 是 1011 的前缀。

非法。

情况 2

当前编码读完了，但当前结点已经有孩子。

例如已有：

现在插：

那么 10 是已有编码前缀。

非法。

情况 3

当前结点本来已经是字符结点。

说明重复编码。

非法。

这道题其实把：

树 + 字符串 + 编码

三个模块结合起来了，非常有 408 大题风格。

五十三、并查集——第 5 章的边缘但应掌握

模拟题把并查集放在树与二叉树应用里。(Any Docs)

并查集本质是：

森林

通常用双亲表示法：

parent[x]

根结点满足：

parent[x] == x

或者使用负数存储集合规模。

Find

int Find(int x) {
    if (parent[x] != x)
        parent[x] = Find(parent[x]);

    return parent[x];
}

其中：

parent[x] = Find(parent[x]);

就是：

路径压缩

Union

先：

rx = Find(x);
ry = Find(y);

如果：

r x = r y

已经同集合。

否则：

小树挂到大树下面。

可以按：

size；
rank；

优化。

路径压缩 + 按秩合并后，均摊时间复杂度接近常数：

O (α (n))

其中 $α (n)$ 是反 Ackermann 函数，实际规模下极小。

五十四、并查集最典型应用

模拟题问：

Floyd、Kruskal、Prim、Dijkstra 哪一个需要并查集？

答案：

Kruskal

(Any Docs)

因为 Kruskal 每加入一条边前都要问：

两端点是不是已经连通？

若：

F in d (u) = F in d (v)

则加入会形成环。

否则：

Union(u, v);

这个知识点会在下一章“图”再次出现。

五十五、这一章算法题究竟应该怎么学？

不要把每个算法分别背。

实际上树算法高度模板化。

模板 A：自顶向下传参数

例如：

深度；
当前路径；
当前和；
当前编码。

典型：

DFS(T, depth + 1);

2014 WPL 就属于这种。

模板 B：自底向上返回信息

例如求：

高度；
子树大小；
是否平衡；
最大值；
WPL。

形式：

left = solve(T->left);
right = solve(T->right);

return combine(left, right);

例如高度：

H (T) = 1 + max (H (T_{L}), H (T_{R}))

模板 C：遍历 + 全局统计

例如：

叶结点数；
度为 2 的结点数；
某层结点数；
最大宽度。

模板 D：后序修改结构

例如：

删除树；
计算子树信息后再处理父结点。

模板 E：层序 + 队列

例如：

层数；
宽度；
完全性；
最浅叶；
按层输出。

只要能识别属于哪一类，很多新算法题都能现场写。

五十六、几道很值得自己再做一次的代表题

如果按“学一道会一类”的目标，建议这一章优先自己独立重做这些：

优先级	题目	能覆盖的题型
S	2016 正则 $k$ 叉树	树的边数、叶结点、高度极值
S	2009 完全二叉树第 6 层叶结点	完全树层数、最大结点数
S	2011 先序/后序题	遍历序列与树形关系
S	2022 中序相邻结点	遍历的局部结构判断
S	2024 $p, v, q$ 中序关系	中序前驱/后继
S	2020 森林遍历转换	树森林 + 二叉树重建
S	2021 森林树数	左孩子右兄弟
S	2021 WPL	哈夫曼构造
S	2012 最优合并	哈夫曼思想迁移
S	2014 求 WPL 算法	二叉树递归大题
S	2017 表达式树	中序递归大题
S	2020 前缀编码 Trie	树与字符串综合

这些题基本覆盖了站内这一章最有代表性的考法。(Any Docs)

五十七、最容易丢分的 15 个陷阱

树的度是最大结点度，不是树高。
一棵树：

E = n - 1

森林则：

E = n - k

二叉树：

n_{0} = n_{2} + 1

与 $n_{1}$ 无关。

完全二叉树不一定是严格二叉树。
哈夫曼树也不一定是完全二叉树。
二叉哈夫曼树不存在度为 1 的结点。
$n$ 个字符的二叉哈夫曼树总结点数：

2 n - 1

完全二叉树叶数：

⌈ \frac{n}{2} ⌉

先序 + 后序一般不能唯一确定二叉树。
如果关键字重复，即使先序 + 中序也可能不能唯一确定树；模拟题的 ooops 就专门利用了重复元素。(Any Docs)
中序前驱是：

左子树最右结点。

中序后继是：

右子树最左结点。

树转二叉树：

左 = 第一个孩子, 右 = 下一个兄弟

树的后根遍历不是对应二叉树后序，而是：

中序

哈夫曼求 WPL 时通常不用画树：

直接累加每次合并值

删除整棵二叉树用：

后序

五十八、值得关注的新考法

结合站内真题的发展，未来这一章很适合继续出现下面几类综合题。

预测 1：遍历 + 算法

例如：

给二叉链表，设计算法判断该树是否为完全二叉树。

核心：

层序 + 队列

属于很自然的 13 分算法题。

预测 2：遍历序列 + 森林转换

已经考过：

森林先根/后根 → 二叉树遍历。

下一步完全可能反过来：

给二叉树先序/中序，求原森林某结点的孩子数、兄弟数、树的棵数。

关键仍然只有一句：

左孩子右兄弟

预测 3： $k$ 叉哈夫曼树

2013 已经考过三叉哈夫曼树，所以不能只掌握二叉。

重点：

(n_{0} - 1) mod (k - 1) = 0

不满足先补零权虚结点。

预测 4：Trie + 编码综合

2020 已经把二进制前缀码和 Trie 结合起来。

以后完全可能问：

给若干编码，设计算法判断是否存在一个编码是另一个的前缀。

最优思维还是 Trie。

预测 5：递归返回多个信息

例如：

一次遍历同时求二叉树的高度与叶结点数。

可以设计结构：

typedef struct {
    int height;
    int leaves;
} Info;

递归返回左右子树信息。

这比单纯背一道算法题更接近现在 408 大题风格。

五十九、最后压缩成考场“思维触发词”

以后做题时，可以这样形成条件反射：

看到什么	第一反应
各种度数结点	$E = n - 1$
二叉树叶结点	$n_{0} = n_{2} + 1$
完全二叉树	编号关系
完全树叶数	$⌈ n /2 ⌉$
完全树高度	$⌊ lo g_{2} n ⌋ + 1$
两种遍历序列	找根、分左右子树
前序+后序	一般不唯一
中序相邻	最右/最左结点
删除树	后序
按层问题	队列
线索	空指针存前驱后继
树转二叉树	左孩子、右兄弟
森林几棵树	根的右链
森林边数	$E = N - k$
哈夫曼	两个最小反复合并
求 WPL	累加合并权值
$n$ 个哈夫曼叶	总结点 $2 n - 1$
多叉哈夫曼	检查 $(n - 1) mod (k - 1)$
最优两两合并	哈夫曼
前缀编码	Trie
Kruskal 判环	并查集

本章最核心的公式清单

真正需要熟练到不思考就能写出的，大概就是这些：

E_{tree} = n - 1

n_{0} = 1 + i \geq 2 \sum (i - 1) n_{i}

n_{0} = n_{2} + 1

N_{m a x}^{(k 叉, h)} = \frac{k ^{h} - 1}{k - 1}

n_{0, 正则 k 叉} = (k - 1) m + 1

n_{complete leaves} = ⌈ \frac{n}{2} ⌉

h_{complete} = ⌊ lo g_{2} n ⌋ + 1

E_{forest} = N - k

W P L = i \sum w_{i} l_{i}

N_{Huffman} = 2 n_{0} - 1

\overset{ˉ}{L} = \frac{W P L}{\sum _{i} w _{i}}

如果这些公式、四种遍历的结构分析、左孩子右兄弟和哈夫曼反复取最小值真正熟练，第 5 章绝大多数选择题就已经有比较稳定的得分能力；再把 2014 WPL、2017 表达式树、2020 Trie 三类递归大题模板吃透，这一章的大题也基本建立起完整框架。站内真题正好覆盖了这几条主线。(Any Docs)

数据结构第 5 章：树与二叉树

On this page