第 5 章树与二叉树

408 数据结构第 5 章树与二叉树复习讲义，涵盖核心概念、重点考点与典型题型。

先建立一个总框架：

树与二叉树
│
├─ 5.1 树
│   ├─ 基本术语
│   └─ 结点数、度、边数、高度关系
│
├─ 5.2 二叉树 ★★★
│   ├─ 二叉树性质
│   ├─ 满二叉树
│   ├─ 完全二叉树 ★★★
│   └─ 顺序/链式存储
│
├─ 5.3 二叉树遍历 ★★★★★
│   ├─ 先序 NLR
│   ├─ 中序 LNR
│   ├─ 后序 LRN
│   ├─ 层序
│   ├─ 根据遍历序列重建二叉树 ★★★★
│   └─ 线索二叉树 ★★★
│
├─ 5.4 树、森林 ★★★
│   ├─ 三种存储
│   ├─ 左孩子—右兄弟
│   └─ 树/森林 ↔ 二叉树
│
└─ 5.5 应用
    ├─ 哈夫曼树、哈夫曼编码 ★★★★
    └─ 并查集 ★★★

其中最值得投入时间的是：

二叉树性质 → 遍历 → 遍历算法题 → 遍历序列重构 → 哈夫曼。

资料也特别强调，遍历是二叉树各种算法操作的基础，历年曾直接结合遍历考算法题。

一、5.1 树的基本概念

1. 什么叫树

树本质上描述的是一种一对多的层次关系。

例如：

A 是根。

A 的孩子是 B、C、D。

B 的孩子是 E、F。

从结构上看，最重要的性质是：

根结点没有双亲；
除根外，每个结点恰好一个双亲；
一个结点可以有任意多个孩子。

因此，一棵有 $n$ 个结点的非空树一定有：

n - 1

条边。

这个结论非常重要。

为什么？

因为除了根以外，其余每个结点都需要“一条从双亲过来的边”。

共有 $n - 1$ 个非根结点，所以就是 $n - 1$ 条边。

二、树中的各种“度”

设结点 A 有 3 个孩子：

        A
      / | \
     B  C  D

那么 A 的度为 3。

结点的度

就是：

这个结点有几个孩子。

树的度

则是：

整棵树中最大的结点度数。

例如某棵树最大的结点有 4 个孩子，那么树的度就是 4。

三、树最重要的数量关系 ★★★

设所有结点的度之和为 $D$ 。

每一个“孩子关系”对应一条边，因此：

D = n - 1

所以：

n = D + 1

这就是大量选择题的底层公式。

典型题型：分支结点的度全部为 $k$

题库中就有：

一棵树共有 $n$ 个结点，所有分支结点的度都为 $k$ ，求叶结点数。

设：

分支结点数为 $x$ ；
叶结点数为 $n_{0}$ 。

因为：

x + n_{0} = n

所有分支结点度数都是 $k$ ，所以总度数：

k x = n - 1

于是：

x = \frac{n - 1}{k}

所以：

n_{0} = n - \frac{n - 1}{k} = \frac{nk - n + 1}{k}

这种题不要专门背答案。

记住：

树的所有度之和 = 边数 = 结点数 − 1。

然后现场列方程即可。

四、 $m$ 叉树的最大结点数

若树的度最大为 $m$ 。

第 1 层最多：

1

第 2 层最多：

m

第 3 层最多：

m^{2}

所以第 $i$ 层最多：

m^{i - 1}

高度为 $h$ 时，结点最多：

1 + m + m^{2} + \dots + m^{h - 1}

即：

\frac{m ^{h} - 1}{m - 1}

最小高度

有 $n$ 个结点，希望树尽可能矮。

怎么办？

当然是：

每一层尽可能塞满。

于是：

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

整理：

n (m - 1) + 1 \leq m^{h}

所以：

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

这是资料明确标注过考点的类型。

五、5.2 二叉树 ★★★★★

二叉树和“度为 2 的树”不能混为一谈。

二叉树规定：

每个结点最多有两个孩子，而且必须区分左孩子和右孩子。

比如：

 A
/
B

和

A
 \
  B

是两棵不同的二叉树。

这件事非常重要。

六、满二叉树

高度为 $h$ 的满二叉树，每一层都达到最大结点数：

        A
      /   \
     B     C
    / \   / \
   D   E F   G

结点总数：

n = 2^{h} - 1

叶结点全部位于最后一层：

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

七、完全二叉树 ★★★★★

完全二叉树是408最喜欢考的特殊二叉树之一。

最直观的理解：

前面每层全部放满，最后一层从左往右连续放置。

例如：

是完全二叉树。

而：

不是。

因为最后一层出现了“左边空、右边有”的洞。

八、完全二叉树编号公式 ★★★★★

按：

从上到下、从左到右

编号：

        1
      /   \
     2     3
    / \   / \
   4  5  6   7

对编号 $i$ ：

双亲

⌊ \frac{i}{2} ⌋

左孩子

2 i

右孩子

2 i + 1

当然前提是这些编号没有超过 $n$ 。

最后一个分支结点

完全二叉树有 $n$ 个结点。

最后一个可能拥有孩子的结点是：

⌊ \frac{n}{2} ⌋

因此：

i \leq ⌊ \frac{n}{2} ⌋

是分支结点，

而：

i > ⌊ \frac{n}{2} ⌋

一定是叶结点。

九、完全二叉树高度 ★★★★

若有 $n$ 个结点：

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

也可以写：

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

理解来源：

高度为 $h$ 时：

2^{h - 1} \leq n < 2^{h}

取对数即可。

十、二叉树最核心公式 ★★★★★

设：

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

总数：

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

另一方面，边数：

n - 1

而度为 1 的结点产生 1 条边，度为 2 的结点产生 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_{2} = 20

那么叶结点一定：

n_{0} = 21

根本不需要知道 $n_{1}$ 。

十一、正则二叉树

正则二叉树规定：

每个结点度只能是 0 或 2。

所以：

n_{1} = 0

又：

n_{0} = n_{2} + 1

总数：

n = n_{0} + n_{2}

代入：

n = 2 n_{0} - 1

所以：

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

题库里就直接有这一类题。

十二、二叉树的存储 ★★★

1. 顺序存储

完全二叉树特别适合数组存储。

因为其编号关系非常规律：

数组下标：1 2 3 4 5 6 7
对应结点：A B C D E F G

马上能找到父子。

资料也指出，完全二叉树顺序存储是高频应用；但普通二叉树如果采用这种方式，可能为了保存结构而插入大量空位置，单支树甚至可能浪费接近指数级空间。

所以：

完全二叉树/堆 → 数组特别合适。

普通二叉树：

链式存储更自然。

十三、二叉链表

基本结构：

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

逻辑结构：

          data
         /    \
    lchild    rchild

十四、二叉链表中的空指针数 ★★★★

有 $n$ 个结点。

每个结点有两个孩子指针，所以总指针域：

2 n

二叉树有：

n - 1

条边。

也就是有 $n - 1$ 个非空指针。

所以空指针：

2 n - (n - 1)

得到：

n + 1

这个结论就是线索二叉树存在的基础。资料也特别指出它常用于选择题。

十五、5.3 二叉树遍历 ★★★★★

这是整个第 5 章最重要的内容。

必须形成这样的条件反射：

先序：根 左 右   NLR
中序：左 根 右   LNR
后序：左 右 根   LRN

注意：

三种遍历，“左子树一定在右子树之前”。

区别只有：

根什么时候访问。

十六、用一棵树彻底搞懂三种遍历

例如：

先序

根 → 左 → 右：

A B D E C F

中序

左 → 根 → 右：

D B E A C F

后序

左 → 右 → 根：

D E B F C A

十七、为什么递归代码几乎一模一样

先序：

void PreOrder(BiTree T) {
    if (T != NULL) {
        visit(T);
        PreOrder(T->lchild);
        PreOrder(T->rchild);
    }
}

中序：

void InOrder(BiTree T) {
    if (T != NULL) {
        InOrder(T->lchild);
        visit(T);
        InOrder(T->rchild);
    }
}

后序：

void PostOrder(BiTree T) {
    if (T != NULL) {
        PostOrder(T->lchild);
        PostOrder(T->rchild);
        visit(T);
    }
}

真正不同的只有 visit(T) 的位置。

因此你最好不要背三个函数。

只背一个通用模板：

void Track(BiTree T) {
    if (T != NULL) {
        // 位置1：先序处理

        Track(T->lchild);

        // 位置2：中序处理

        Track(T->rchild);

        // 位置3：后序处理
    }
}

这正是资料最后归纳总结特别强调的算法思想。

十八、算法题真正怎么考 ★★★★★

408并不一定问：

“写一个先序遍历。”

更可能问：

利用二叉树遍历，完成某项统计或修改。

所以最关键的问题变成：

我应该在递归过程中返回什么？

十九、典型算法 1：统计叶结点数

叶结点定义：

T->lchild == NULL && T->rchild == NULL

于是：

int LeafCount(BiTree T) {
    if (T == NULL)
        return 0;

    if (T->lchild == NULL && T->rchild == NULL)
        return 1;

    return LeafCount(T->lchild)
         + LeafCount(T->rchild);
}

理解：

整棵树叶结点数 = 左子树叶数 + 右子树叶数。

这是典型的“分治 + 递归”。

二十、典型算法 2：求二叉树高度 ★★★★★

核心思想：

一棵树的高度 = 左右子树最大高度 + 1。

所以：

int Height(BiTree T) {
    if (T == NULL)
        return 0;

    int left = Height(T->lchild);
    int right = Height(T->rchild);

    return (left > right ? left : right) + 1;
}

公式：

H (T) = {0, 1 + max (H (T_{L}), H (T_{R})), T = \emptyset T \neq = \emptyset

题库也专门出现了这种代码的复杂度题：虽然树高可能只有对数级，但函数仍访问所有结点，所以时间复杂度是 $O (n)$ ，而不是 $O (lo g n)$ 。

二十一、典型算法 3：交换所有左右子树

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

    BiTree temp = T->lchild;
    T->lchild = T->rchild;
    T->rchild = temp;

    Swap(T->lchild);
    Swap(T->rchild);
}

本质：

每个结点访问一次，并交换两条指针。

时间：

O (n)

二十二、典型算法 4：删除整棵树

这个地方非常适合理解为什么需要后序。

如果你先删除根：

delete(root)

那你连左右子树指针都可能丢掉。

所以应该：

先删左
先删右
最后删自己

也就是后序遍历思想。

void Destroy(BiTree T) {
    if (T != NULL) {
        Destroy(T->lchild);
        Destroy(T->rchild);
        free(T);
    }
}

这就是：

“处理一个对象之前，需要先处理它依赖的子对象”

时典型使用后序。

二十三、层序遍历 ★★★★

层序遍历不是递归，而是：

一层一层从左到右。

使用队列。

根入队

while 队列不空：
    出队 p
    访问 p
    左孩子存在 → 入队
    右孩子存在 → 入队

代码：

void LevelOrder(BiTree T) {
    InitQueue(Q);

    if (T != NULL)
        EnQueue(Q, T);

    while (!IsEmpty(Q)) {
        BiTree p;
        DeQueue(Q, p);

        visit(p);

        if (p->lchild != NULL)
            EnQueue(Q, p->lchild);

        if (p->rchild != NULL)
            EnQueue(Q, p->rchild);
    }
}

为什么是队列

因为第二层结点：

B C

要按照进入顺序：

B → C

继续扩展。

这正是 FIFO。

题库中甚至直接给出一棵树，要求根据先序结果判断另一个序列是什么遍历，答案就是层序。

二十四、由遍历序列重建二叉树 ★★★★★

这是非常经典的综合题。

先记结论：

可以唯一确定

先序 + 中序
后序 + 中序
层序 + 中序

通常不能唯一确定

先序 + 后序
先序 + 层序
后序 + 层序

核心原因：

中序序列能够告诉你左子树和右子树的边界。

二十五、先序 + 中序重建 ★★★★★

例如：

先序：

A B D E C F

中序：

D B E A C F

先序第一个一定是根：

去中序中找 A：

D B E | A | C F

于是：

左子树：D B E
右子树：C F

因为左子树 3 个结点，所以回先序：

A | B D E | C F

左子树先序：

B D E

右子树先序：

C F

继续递归。

做题口诀

先序 + 中序

先序找根，中序切左右。

后序 + 中序

后序末尾找根，中序切左右。

整个算法就是不停递归。

二十六、为什么“先序 + 后序”不够

假设：

先序：

A B

后序：

B A

可能是：

 A
/
B

也可能是：

A
 \
  B

两棵不同的树。

所以无法唯一确定。

二十七、线索二叉树 ★★★

这一部分刚学时容易觉得抽象，其实目的只有一句话：

把原本浪费的空指针拿来记录遍历序列中的前驱和后继。

前面已经知道：

$n$ 个结点的二叉链表有：

n + 1

个空指针。

既然空着，不如利用。

二十八、中序线索二叉树

普通结点：

lchild | data | rchild

线索结点增加：

lchild | ltag | data | rtag | rchild

规定：

左边

ltag = 0 → lchild 是左孩子
ltag = 1 → lchild 是中序前驱

右边

rtag = 0 → rchild 是右孩子
rtag = 1 → rchild 是中序后继

一定要记：

tag = 0 是真正的孩子 tag = 1 是线索

二十九、线索化的本质 ★★★★

线索化不是一种神秘算法。

本质就是：

遍历二叉树的同时记录上一个访问的结点。

例如中序：

D B E A C F

当现在访问 E：

pre = B
p   = E

因此：

B 是 E 的中序前驱
E 是 B 的中序后继

如果相关指针为空，就把它改为线索。

核心代码思想：

if (p->lchild == NULL) {
    p->lchild = pre;
    p->ltag = 1;
}

if (pre != NULL && pre->rchild == NULL) {
    pre->rchild = p;
    pre->rtag = 1;
}

pre = p;

三十、中序线索树怎么找后继 ★★★★

假设当前是 $p$ 。

情况 1：有后继线索

即：

p->rtag == 1

那么：

p->rchild

直接就是后继。

情况 2：有真正的右子树

即：

p->rtag == 0

根据中序：

左 根 右

访问完 $p$ 后，要进入它的右子树。

而右子树里首先访问谁？

最左下的结点。

因此：

后继 = 右子树最左结点

这个规则必须会。

三十一、为什么后序线索树查后继比较麻烦

这是很好的理解题。

后序：

左 → 右 → 根

当前结点访问结束后，有时要回到双亲。

但普通二叉链表：

结点 → 孩子

并没有：

孩子 → 双亲

所以可能无法直接回去。

因此资料强调：

后序线索二叉树若想高效求后继，常常还需要双亲信息。

这也是题库中“线索化后仍不能有效解决什么问题”的常见判断方向。

三十二、5.4 树的存储结构

这一块不难，重点理解“哪种查什么方便”。

双亲表示法

数组中每个结点记录：

data + parent

例如：

index   data   parent
0       A      -1
1       B       0
2       C       0
3       D       1

优点：

找双亲非常快。

因为：

nodes[i].parent

直接就是。

缺点：

找所有孩子麻烦。

得扫描整个数组。

资料也特别比较了这一点。

三十三、孩子表示法

反过来：

每个结点维护自己的孩子链表。

例如：

A → B → C → D
B → E → F

优点：

找孩子方便。

缺点：

找双亲不方便。

所以可以把两种方式看成：

存储	找双亲	找孩子
双亲表示法	快	慢
孩子表示法	慢	快

三十四、孩子兄弟表示法 ★★★★

这是非常重要的结构，因为它直接通向：

树 ↔ 二叉树。

结点：

typedef struct CSNode {
    ElemType data;
    struct CSNode *firstchild;
    struct CSNode *nextsibling;
} CSNode;

含义：

左指针 = 第一个孩子
右指针 = 下一个兄弟

记成一句：

左孩子，右兄弟。

资料正是用这种方式把一般树映射为二叉树。

三十五、树转换成二叉树 ★★★★

例如原树：

        A
      / | \
     B  C  D
    / \
   E   F

按照：

左孩子，右兄弟

得到：

注意这里：

A 的左孩子 B = A 的第一个孩子；
B 的右孩子 C = B 的下一个兄弟；
C 的右孩子 D = C 的下一个兄弟；
B 的左孩子 E；
E 的右孩子 F。

三十六、树转二叉树的一个高频性质

因为原树的根没有兄弟，所以：

树转成的二叉树，其根一定没有右子树。

这个很容易出判断题。

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

假设森林：

T1    T2    T3

三棵树的根：

A     B     C

转换后：

A
 \
  B
   \
    C

也就是说：

森林中不同树的根，也当作兄弟处理。

所以：

第一棵树根 → 二叉树根；
第二棵树根 → 第一棵根的右孩子；
第三棵树根 → 第二棵根的右孩子。

题库中就直接问：

三棵树结点数分别为 $M_{1}, M_{2}, M_{3}$ ，转换后根的右子树有多少结点？

答案显然：

M_{2} + M_{3}

因为第一棵树对应根和根的左子树，后两棵都进入右子树。

三十八、树、森林与二叉树的遍历对应 ★★★

这是一个很适合直接记忆的表。

原结构	遍历	对应二叉树
树	先根	先序
树	后根	中序
森林	先序	先序
森林	中序	中序

尤其记：

树的后根遍历 = 对应二叉树的中序遍历。

很多人会误认为对应后序，这里很容易丢分。

三十九、5.5 哈夫曼树 ★★★★★

先理解它究竟优化什么。

假设有四个字符：

A 出现 50 次
B 出现 25 次
C 出现 15 次
D 出现 10 次

显然：

A 最常见，所以最好用最短编码。

D 最少见，可以用长一些。

哈夫曼树就是在做：

让权值大的叶子靠近根，权值小的叶子远离根。

从而让总体代价最小。

四十、WPL

设叶结点 $i$ ：

权值 $w_{i}$ ；
到根的路径长度 $l_{i}$ 。

带权路径长度：

w_{i} l_{i}

整棵树：

WPL = i = 1 \sum n w_{i} l_{i}

哈夫曼树就是：

WPL 最小的二叉树。

四十一、哈夫曼树构造过程 ★★★★★

给权值：

2, 4, 5, 7

每一步：

选当前最小两个。

第一步

最小：

2, 4

合并：

2 + 4 = 6

现在：

5, 6, 7

第二步

最小：

5, 6

合并：

5 + 6 = 11

现在：

7, 11

第三步

合并：

7 + 11 = 18

最终：

四十二、WPL 怎么算

路径长度：

7 深度 1；
5 深度 2；
2 深度 3；
4 深度 3。

所以：

WPL = 7 \times 1 + 5 \times 2 + 2 \times 3 + 4 \times 3

即：

WPL = 35

四十三、哈夫曼树的重要性质 ★★★★

若有 $n$ 个初始权值。

这些全部最终成为叶子。

每次：

两棵树 → 新建一个双亲

最后需要合并：

n - 1

次。

所以新建：

n - 1

个分支结点。

总结点：

n + (n - 1) = 2 n - 1

所以：

2 n - 1

必为奇数。

同时不存在度为 1 的结点

因为每次新结点都同时连接两棵树。

所以：

度只有 0 和 2

即：

二叉哈夫曼树是正则二叉树。

因此：

n_{0} = n_{2} + 1

四十四、哈夫曼树并不一定唯一

如果出现相同权值：

2, 2, 3, 3

选择顺序可能不同。

而且左右孩子也可以交换。

因此：

树形可能不同。

编码：

也可能不同。

高度：

甚至可能不同。

但是有一样东西不会变：

最小 WPL

题库就专门考查“一组权值对应的哈夫曼树可能不唯一、高度也可能不唯一”。

四十五、哈夫曼编码 ★★★★

规定：

左边 = 0
右边 = 1

例如：

则：

A = 0
B = 10
C = 11

四十六、为什么哈夫曼编码一定是前缀编码

前缀编码要求：

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

因为字符只放在叶结点。

假设 A 编码对应一个叶子：

那么这条路径到 A 就结束了。

A 下面不可能再有：

00
01

对应其他字符。

所以天然没有前缀冲突。

四十七、前缀编码题怎么想

题库中有典型题：

已有字符编码 0 和 10，编码长度最多 4，还能编码多少字符？

因为 0 已经作为一个完整编码：

0xxx

全部不能再用。

10 也已经占据一棵子树：

10xx

也不能用。

剩余只剩：

为了容纳最多字符，把它扩展到长度 4：

因此最多还能有：

4

个字符。题库解析也是按这一思路处理。

四十八、 $m$ 叉哈夫曼树的数量关系

题库还涉及一般 $m$ 叉哈夫曼树。

若：

叶结点 $n_{0}$ ；
非叶结点 $n_{m}$ ；
每个非叶结点度都是 $m$ 。

边数一方面：

m n_{m}

另一方面：

n_{0} + n_{m} - 1

所以：

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

整理：

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

因此：

n_{m} = \frac{n _{0} - 1}{m - 1}

二叉树 $m = 2$ 时自然退化为：

n_{2} = n_{0} - 1

四十九、并查集 ★★★★

并查集名字虽然奇怪，本质非常简单：

管理若干互不相交的集合。

核心只解决两个问题：

Find

x 属于哪个集合？

Union

把两个集合合并。

五十、并查集为什么用树

例如：

集合1：{0,1,2}
集合2：{3,4}

可以表示：

    0           3
   / \          |
  1   2         4

每棵树代表一个集合。

根代表这个集合。

五十一、并查集数组表示

例如：

下标： 0  1  2  3  4
值：  -3  0  0 -2  3

解释：

S[1] = 0

表示：

1 的双亲是 0。

S[2] = 0

表示：

2 的双亲是 0。

而：

S[0] = -3

负数表示：

0 是根。

绝对值：

3

表示这个集合有 3 个元素。

五十二、Find

int Find(int S[], int x) {
    while (S[x] >= 0)
        x = S[x];

    return x;
}

就是：

不停找爸爸
→ 找爸爸的爸爸
→ 找爸爸的爸爸的爸爸
→ 直到根

例如：

5 → 3 → 1 → 0

那么：

Find(5) = 0

五十三、Union

如果：

Root1 = 0
Root2 = 3

直接：

S[Root2] = Root1;

即：

3 → 0

两棵树就合成一个集合。

五十四、并查集为什么要优化 ★★★★

如果每次乱挂：

Find(4) 要：

4→3→2→1→0

变成：

O (n)

很差。

所以有两个重要优化。

五十五、优化一：小树挂大树

例如：

集合 A：100 个结点
集合 B：2 个结点

不要把 A 挂在 B 下面。

应该：

B → A

即：

小树挂到大树根下面。

这样树不容易变深。

资料中给出的按大小合并后，树高可以控制在对数级附近。

五十六、优化二：路径压缩 ★★★★★

假设：

6 → 5 → 3 → 1 → 0

第一次：

Find(6)

已经知道最终根是 0。

那以后何必还绕路？

直接变成：

    0
  / | | \
 1  3 5  6

即：

6 → 0
5 → 0
3 → 0

这叫：

路径压缩。

路径压缩最经典的递归写法

int Find(int x) {
    if (parent[x] < 0)
        return x;

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

关键不是前半句。

真正精彩的是：

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

它意味着：

找到最终根；
把自己的 parent 直接改成根。

查找和压缩同时完成。

五十七、并查集和 Kruskal ★★★★

题库直接考：

哪个算法需要并查集？

答案：

Kruskal 最小生成树算法。

为什么？

Kruskal 不断选择最小边：

u —— v

但必须判断：

加入这条边会不会形成环？

判断方法：

Find(u) == Find(v)

说明：

u 和 v 本来已经连通。

此时再加边一定形成环。

如果：

Find(u) != Find(v)

说明属于不同连通分量：

可以加边
然后 Union(u,v)

所以整个逻辑就是：

for 每条由小到大的边(u,v):
    if Find(u) != Find(v):
        选这条边
        Union(u,v)

这也是并查集在408中最重要的应用。

五十八、这一章的算法题，你真正应该掌握什么

资料最后列出了很多典型递归问题，包括统计不同度结点、求高度、宽度、删除叶子、计算层次、求最大值、交换左右孩子等。

不要把它们背成十道独立算法。

它们其实都是一个东西：

Solve(T) {
    if (T == NULL)
        ...

    // 根的处理

    Solve(T->lchild);

    // 根的处理

    Solve(T->rchild);

    // 根的处理
}

你真正要判断的是：

第一问：空树返回什么？

例如高度：

叶结点数：

第二问：左右子树给我什么信息？

高度问题：

左右子树高度

叶数问题：

左右子树叶数

最大值：

左右子树最大值

第三问：怎么合并左右答案？

高度：

max (L, R) + 1

叶数：

L + R

总结点：

L + R + 1

这才是二叉树算法题的核心。

五十九、这一章最容易混淆的 10 个点

二叉树 ≠ 度为 2 的树。
完全二叉树最后一层必须从左向右连续。
二叉树：

n_{0} = n_{2} + 1

和 $n_{1}$ 没关系。

二叉链表的空指针数：

n + 1

先序、中序、后序的左右顺序始终都是：

左在右前

只是根的位置不同。

先序 + 后序通常不能唯一确定二叉树。
有中序 + 另一个序列通常才可以唯一划分左右子树。
树转换二叉树：

左孩子，右兄弟

树的后根遍历对应二叉树的：

中序，不是后序。

哈夫曼树可能不唯一，但：

WPL

的最优值一致。

六十、按照408优先级复习

第一梯队：必须非常熟

1. 二叉树性质

尤其：

n_{0} = n_{2} + 1

完全二叉树编号：

p a r e n t (i) = ⌊ \frac{i}{2} ⌋

l e f t (i) = 2 i

r i g h t (i) = 2 i + 1

高度：

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

2. 四种遍历

先序 NLR
中序 LNR
后序 LRN
层序 Queue

必须做到看到树就能迅速写序列。

3. 二叉树递归算法

至少熟练：

统计结点
统计叶子
统计度1/度2
求高度
交换左右子树
删除树
查找结点

资料明确指出这里是统考算法题重点。

4. 根据序列构造树

必须熟练：

先序 + 中序
后序 + 中序
层序 + 中序

最重要技巧：

找根 → 中序分左右 → 递归。

六十一、第二梯队：选择题高频

完全二叉树性质

二叉链表空指针

线索二叉树

树/森林与二叉树转换

哈夫曼树

哈夫曼编码

这些在你这里的题库中几乎都有单独对应题型。

六十二、第三梯队：理解为主

树的：

双亲表示法；
孩子表示法；
一般术语。

不需要花太多时间死背代码。

理解：

双亲表示 → 找爸爸快
孩子表示 → 找孩子快
孩子兄弟 → 方便转换二叉树

基本足够。

最后给出一张“第5章考场公式表”

树

边数 = n - 1

\sum 结点度 = n - 1

高度为 $h$ 的 $m$ 叉树最大结点数：

\frac{m ^{h} - 1}{m - 1}

二叉树

n_{0} = n_{2} + 1

第 $k$ 层最大结点数：

2^{k - 1}

高度为 $h$ 最大结点数：

2^{h} - 1

完全二叉树高度：

⌊ lo g_{2} n ⌋ + 1

二叉链表空指针：

n + 1

完全二叉树编号

p a r e n t (i) = ⌊ \frac{i}{2} ⌋

l e f t (i) = 2 i

r i g h t (i) = 2 i + 1

遍历

先序：NLR
中序：LNR
后序：LRN
层序：队列

哈夫曼

WPL = \sum w_{i} l_{i}

$n$ 个叶结点的二叉哈夫曼树：

2 n - 1

个总结点。

一般满 $m$ 叉结构：

n_{非叶} = \frac{n _{叶} - 1}{m - 1}

并查集

Find：找根
Union：合并根
优化1：小树挂大树
优化2：路径压缩
Kruskal：用并查集判环

如果第 5 章只抓一条主线来学，就抓：

二叉树的递归结构 → 遍历 → 利用遍历处理问题 → 根据遍历重建结构。

一旦这条主线真正理解了，树这一章的大多数算法题就不再是“背代码”，而只是决定递归返回什么、在哪个位置处理根结点、左右子树答案怎么合并。

第 5 章 树与二叉树

On this page

第 5 章树与二叉树