Lecture 18：树、森林

18.1 树的存储结构

18.1.1 双亲表示法

定义：#双亲表示法

描述： 双亲表示法是一种顺序存储结构。它用数组存储树中各个结点，并在每个结点中保存该结点双亲在数组中的下标。

基本思想

• 每个结点中保存一个指向双亲的“指针”。
• 在顺序表中，这个指针实际保存的是双亲结点在数组中的下标。
• 根结点没有双亲，因此根结点的 parent 通常记为： $$ -1 $$

PDF 示例

含义

• B 的 parent=0，说明 B 的双亲是下标为 0 的结点 A。
• E 的 parent=1，说明 E 的双亲是下标为 1 的结点 B。
• K 的 parent=4，说明 K 的双亲是下标为 4 的结点 E。

优点

• 查指定结点的双亲很方便。
• 可以直接通过下标找到双亲结点。
• 也可以存储森林：把多棵树的根结点 parent 都设为 -1。

缺点

• 查指定结点的孩子不方便。
• 若要找某个结点的所有孩子，需要从头扫描整个数组。
• 因此它适合经常找双亲、不经常找孩子的场景。

复杂度口径

• 已知结点在数组中的下标时，读取 parent 并定位双亲是 $O(1)$。
• 查一个结点的全部孩子通常要扫描整个数组，是 $O(n)$。
• 如果只给出关键字、还要先在数组中查到该结点，则查找关键字本身也可能需要 $O(n)$；不能脱离“已知下标”的前提笼统地说查双亲必为 $O(1)$。

图示说明

• 左侧数组的 parent 保存双亲下标，右侧箭头由孩子指向双亲。
• A 的 parent=-1，所以 A 是根；B、C、D 的 parent 都是 0，所以它们都是 A 的孩子。

双亲表示法代码

#define MAX_TREE_SIZE 100

typedef struct {
    ElemType data;  // 数据元素
    int parent;     // 双亲位置域，指明双亲在数组中的下标
} PTNode;

typedef struct {
    PTNode nodes[MAX_TREE_SIZE]; // 双亲表示
    int n;                       // 结点数
} PTree;

代码理解

• nodes[i].data 保存第 i 个结点的数据。
• nodes[i].parent 保存第 i 个结点的双亲下标。
• 根结点的 parent 为 -1。

18.1.2 孩子表示法

定义：#孩子表示法

描述： 孩子表示法使用数组顺序存储各个结点，同时为每个结点建立一个孩子链表，用来保存该结点所有孩子在数组中的位置。

存储方式

• 用数组顺序存储所有结点。
• 数组中的每个结点保存：
  • 数据元素。
  • 孩子链表头指针。
• 孩子链表中的每个结点保存：
  • 某个孩子结点在数组中的下标。
  • 指向下一个孩子链表结点的指针。

PDF 示例理解

• A 结点的孩子是 B C D。
• 在孩子表示法中，A 的 firstChild 指向一个孩子链表。
• 这个孩子链表依次保存 B、C、D 在数组中的下标。

优点

• 查某个结点的所有孩子很方便。
• 沿着该结点的孩子链表即可找到所有孩子。

缺点

• 查某个结点的双亲不方便。
• 若没有额外保存双亲信息，仍然需要扫描各个孩子链表。

复杂度口径

• 已知结点数组下标时，枚举它的孩子只需遍历本结点的孩子链表，时间为 $O(d)$，其中 $d$ 是该结点的度。
• 若结构中没有双亲域，反查某结点的双亲通常要检查各条孩子链，最坏为 $O(n)$。

存储森林时的注意

• 孩子表示法可以存储森林。
• 但需要额外记录多个根结点的位置。
• PDF 中代码用 r 记录根位置；若是森林，则需要记录多个根位置。

图示说明

• 数组保存结点数据和孩子链表头指针；橙色链结点保存孩子在数组中的下标。
• 例如 A 的孩子链依次为 1 -> 2 -> 3，对应孩子 B、C、D。

孩子表示法代码

struct CTNode {
    int child;              // 孩子结点在数组中的位置
    struct CTNode *next;    // 下一个孩子
};

typedef struct {
    ElemType data;
    struct CTNode *firstChild; // 第一个孩子
} CTBox;

typedef struct {
    CTBox nodes[MAX_TREE_SIZE];
    int n, r;                  // 结点数和根位置
} CTree;

代码理解

• CTBox 是数组中的一个结点框。
• firstChild 指向该结点的第一个孩子链表结点。
• CTNode.child 存的是孩子在数组中的位置，不是孩子的数据本身。

18.1.3 孩子兄弟表示法

定义：#孩子兄弟表示法

描述： 孩子兄弟表示法是一种链式存储结构。每个结点保存两个指针：一个指向第一个孩子，另一个指向右边的第一个兄弟。

两个指针

• firstchild：指向该结点的第一个孩子。
• nextsibling：指向该结点右边的第一个兄弟。

与二叉链表的关系

• 形式上和二叉树的二叉链表类似。
• 都是一个数据域加两个指针域。
• 但两个指针的含义不同。

核心口诀

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

优点

• 可以用熟悉的二叉树操作来处理树和森林。
• 树、森林与二叉树之间的转换，本质上依赖孩子兄弟表示法。

森林中的特殊含义

• 森林中每棵树的根结点可以看作平级兄弟。
• 因此多个根结点之间可以用右指针串起来。

操作特点

• 已知结点时，找第一个孩子和下一个兄弟都是 $O(1)$。
• 若不额外保存双亲指针，找双亲通常仍需从根遍历，最坏为 $O(n)$。

图示说明

• 蓝色边表示“第一个孩子”，黄色边表示“下一个兄弟”。
• 森林中各棵树的根也按兄弟关系用右指针相连，因此整片森林可以用一棵二叉树形态表示。

孩子兄弟表示法代码

typedef struct CSNode {
    ElemType data;                         // 数据
    struct CSNode *firstchild, *nextsibling; // 第一个孩子和右兄弟指针
} CSNode, *CSTree;

代码理解

• firstchild 可以看作二叉树中的左指针。
• nextsibling 可以看作二叉树中的右指针。
• 但语义一定要按“孩子、兄弟”理解，不能误解成二叉树的左孩子、右孩子。

18.1.4 三种存储结构对比

18.2 树和森林的遍历

IMPORTANT · 孩子次序前提 下列遍历序列和转换结果都依赖固定的孩子次序。408 题目中的树通常按从左到右有序；若讨论无序树，必须先约定孩子排列顺序，否则遍历序列和对应二叉树并不唯一。

18.2.1 树的先根遍历

定义：#树的先根遍历

描述： 若树非空，先访问根结点，再依次对每棵子树进行先根遍历。

访问顺序

根 -> 第 1 棵子树 -> 第 2 棵子树 -> ... -> 第 k 棵子树

递归过程

1. 访问根结点。
2. 按从左到右的顺序，对每棵子树进行先根遍历。

重要对应关系

• 树的先根遍历序列，与这棵树转换得到的二叉树的先序遍历序列相同。

代码

void PreOrder(CSTree R) {
    if (R != NULL) {
        visit(R);                            // 访问根结点
        for (CSTree child = R->firstchild; child != NULL;
             child = child->nextsibling) {
            PreOrder(child);                 // 按顺序遍历每棵子树
        }
    }
}

这里沿用上文的 CSNode/CSTree 孩子兄弟结点定义，visit 表示由使用者提供的访问操作；只沿 firstchild 进入子树，由本层循环沿 nextsibling 枚举兄弟。

记忆

• 树的“先根”对应二叉树的“先序”。
• 根先访问，所以和二叉树先序遍历一致。

18.2.2 树的后根遍历

定义：#树的后根遍历

描述： 若树非空，先依次对每棵子树进行后根遍历，最后再访问根结点。

访问顺序

第 1 棵子树 -> 第 2 棵子树 -> ... -> 第 k 棵子树 -> 根

递归过程

1. 按从左到右的顺序，对每棵子树进行后根遍历。
2. 最后访问根结点。

重要对应关系

• 树的后根遍历序列，与这棵树转换得到的二叉树的中序遍历序列相同。
• 原因：在孩子兄弟表示法中，结点的左指针指向第一个孩子，右指针指向下一个兄弟。树根没有右兄弟，因此转换后二叉树的根没有右子树；中序遍历先访问根的左子树（其中编码了原树根的各棵子树及兄弟链），再访问根，正好得到原树的后根遍历。

代码

void PostOrder(CSTree R) {
    if (R != NULL) {
        for (CSTree child = R->firstchild; child != NULL;
             child = child->nextsibling) {
            PostOrder(child);                // 先遍历各棵子树
        }
        visit(R);                            // 最后访问根结点
    }
}

记忆

• 树的“后根”对应二叉树的“中序”。
• 这是本节常考对应关系之一。

18.2.3 森林的先序遍历

定义：#森林先序遍历

描述： 若森林非空，先访问森林中第一棵树的根结点，再先序遍历第一棵树根结点的子树森林，最后先序遍历去除第一棵树后剩余树构成的森林。

访问规则

1. 访问森林中第一棵树的根结点。
2. 先序遍历第一棵树中根结点的子树森林。
3. 先序遍历去除第一棵树之后剩余树构成的森林。

重要对应关系

• 森林的先序遍历序列，与森林转换得到的二叉树的先序遍历序列相同。
• 做题时可以先转换成二叉树，再求先序遍历。

18.2.4 森林的中序遍历

定义：#森林中序遍历

描述： 若森林非空，先中序遍历森林中第一棵树根结点的子树森林，再访问第一棵树的根结点，最后中序遍历去除第一棵树后剩余树构成的森林。

访问规则

1. 中序遍历森林中第一棵树根结点的子树森林。
2. 访问第一棵树的根结点。
3. 中序遍历去除第一棵树之后剩余树构成的森林。

重要对应关系

• 森林的中序遍历序列，与森林转换得到的二叉树的中序遍历序列相同。

18.2.5 遍历对应关系总结

易错点

• 树没有“中根遍历”这一常用说法，树常说先根、后根。
• 森林常说先序、中序。
• 树的后根遍历不是对应二叉树后序，而是对应二叉树中序。

18.3 树、森林与二叉树的转换

18.3.1 核心原则

树、森林与二叉树转换的核心是孩子兄弟表示法：

第一个孩子 -> 左指针
右边兄弟   -> 右指针

也可以记为：

左孩子右兄弟

“糖葫芦”理解

• 同一组兄弟结点用右指针串成一串。
• 这串兄弟链就是 PDF 中说的“右指针糖葫芦”。
• 第一个孩子挂在父结点的左指针下。
• 后续兄弟依次挂在前一个兄弟的右指针上。

18.3.2 树转二叉树

定义：#树转二叉树

描述： 将一棵普通树按孩子兄弟表示法转换成一棵二叉树。

转换方法

1. 先在二叉树中画出原树的根结点。
2. 按树的层序，从上到下、从左到右依次处理每个结点。
3. 如果当前结点在树中有孩子：
   • 把所有孩子结点用右指针串成一串。
   • 把第一个孩子挂到当前结点的左指针下。
4. 重复直到所有结点处理完。

处理一个结点的口诀

孩子排成右链
第一个孩子挂左边

例子 若树中 A 的孩子依次为：

B C D

则在二叉树中：

• A->lchild = B
• B->rchild = C
• C->rchild = D

画成结构：

    A
   /
  B
   \
    C
     \
      D

注意

• 原树中的兄弟关系，在二叉树中表现为右孩子关系。
• 原树中的第一个孩子，在二叉树中表现为左孩子关系。

图示说明

• 原树中同一父结点的孩子按从左到右的次序排列；转换后，第一个孩子成为左孩子，其余兄弟沿右指针依次相连。
• 图中的黄色边表示由兄弟关系形成的右指针。

18.3.3 森林转二叉树

定义：#森林转二叉树

描述： 将森林中的多棵树按孩子兄弟表示法合并表示为一棵二叉树。

转换方法

1. 先把森林中所有树的根结点画出来。
2. 在二叉树中，用右指针把这些根结点串成一串。
3. 按森林的层序依次处理每个结点。
4. 如果当前结点在原树中有孩子：
   • 把所有孩子结点用右指针串成一串。
   • 把第一个孩子挂在当前结点的左指针下。

根结点的处理 若森林有三棵树，根分别为：

A C F

则在二叉树中：

A ->right C ->right F

即：

A
 \
  C
   \
    F

注意

• 森林中各棵树的根结点视为平级兄弟关系。
• 在转换后的二叉树中，右指针表示平级关系。
• 转换后二叉树的左边表示“第一个孩子”关系，右边表示“下一个兄弟”关系；必须结合边的方向解释原森林关系。

图示说明

• A、C、F、L 是四棵树的根，在二叉树中沿根结点右链相连。
• 每棵树内部仍执行“第一个孩子接左边、其余兄弟接右边”。

18.3.4 二叉树转树

定义：#二叉树转树

描述： 将由一棵树转换得到的二叉树，按左孩子右兄弟规则还原为原来的树。

转换方法

1. 先画出树的根结点。
2. 从根结点开始，按树的层序顺序，一层一层恢复每个结点的孩子。
3. 在二叉树中，如果当前处理的结点有左孩子：
   • 把左孩子和从它开始的一整串右指针链拆下来。
   • 按顺序挂在当前结点的下方，作为当前结点的孩子。
4. 重复直到所有结点处理完。

反向口诀

左孩子是第一个孩子
右链是同一组兄弟

例子 若二叉树中有：

A->lchild = B
B->rchild = C
C->rchild = D

则还原为树时：

• B C D 都是 A 的孩子。
• 它们不是二叉树意义上的右孩子关系，而是原树中的兄弟关系。

注意

• 任意二叉树都可以按“左孩子、右兄弟”解释为一片森林。
• 只有当二叉树根结点的右指针为空时，解释结果才是一棵树；若根的右指针非空，则根及其右链对应森林中的多个树根。

图示说明

• 二叉树根 A 没有右兄弟，所以还原结果是一棵树。
• 每个结点的左孩子及其右链，被还原为该结点从左到右的一组孩子。

18.3.5 二叉树转森林

定义：#二叉树转森林

描述： 将由森林转换得到的二叉树，按左孩子右兄弟规则还原为多棵树组成的森林。

转换方法

1. 先把二叉树的根结点和从根结点开始的一整串右指针链拆下来。
2. 这些结点作为森林中多棵树的根结点。
3. 按森林的层序恢复每个结点的孩子。
4. 在二叉树中，如果当前处理的结点有左孩子：
   • 把左孩子和从左孩子开始的一整串右指针链拆下来。
   • 按顺序挂在当前结点的下方，作为它的孩子。

核心

右指针糖葫芦 = 平级关系

还原规则

• 根结点的右指针链，对应森林中多棵树的根。
• 某个结点左孩子开始的右指针链，对应该结点的一组孩子。

图示说明

• 二叉树根 A 的右链还包含 C、F、L，因此还原为以 A、C、F、L 为根的四棵树。
• 对每个根和内部结点，再按“左孩子是第一个孩子、右链是其余兄弟”恢复各自的孩子。

18.4 题型：树、森林与二叉树转换

题型一：判断存储方式特点

第一部分：解题方法

看到题干描述后，抓关键词：

第二部分：典型例题

例 1 某树的存储结构中，每个结点保存 data 和 parent 两个域，parent 保存双亲结点在数组中的位置。该结构是什么？

答案

• 双亲表示法。

例 2 某树的存储结构中，每个结点保存 firstchild 和 nextsibling 两个指针。该结构是什么？

答案

• 孩子兄弟表示法。

第三部分：知识点复盘

• 双亲表示法查父结点快。
• 孩子表示法查孩子快。
• 孩子兄弟表示法最适合和二叉树互相转换。

题型二：树和森林遍历对应二叉树遍历

第一部分：解题方法

记住对应关系：

第二部分：典型例题

例 1 一棵树转换为二叉树后，对该二叉树进行先序遍历，所得序列等于原树的什么遍历？

答案

• 原树的先根遍历。

例 2 一棵树转换为二叉树后，对该二叉树进行中序遍历，所得序列等于原树的什么遍历？

答案

• 原树的后根遍历。

第三部分：知识点复盘

• 树后根对应二叉树中序，这是常见易错点。
• 森林先序对应二叉树先序。
• 森林中序对应二叉树中序。

题型三：树转二叉树

第一部分：解题方法

1. 从原树根结点开始。
2. 每个结点的第一个孩子，变成该结点的左孩子。
3. 每个结点的其余孩子，用右指针依次串起来。
4. 对所有结点重复。

第二部分：典型例题

若原树中：

A 的孩子：B C D
B 的孩子：E F
C 的孩子：G

则二叉树中：

A->lchild = B
B->rchild = C
C->rchild = D
B->lchild = E
E->rchild = F
C->lchild = G

第三部分：知识点复盘

• 原树同一父结点的多个孩子，在二叉树中构成右指针链。
• 原树的第一个孩子才是二叉树中的左孩子。

题型四：二叉树还原树或森林

第一部分：解题方法

1. 先看二叉树根结点的右指针是否为空。
2. 若根的右指针非空，则根及其右链表示多个平级根，还原为森林。
3. 若根的右指针为空，则还原为一棵树。
4. 对每个结点：
   • 左孩子是第一个孩子。
   • 左孩子开始的整串右指针链，是该结点的所有孩子。

第二部分：典型例题

若二叉树中：

A->lchild = B
B->rchild = C
C->rchild = D

则在还原后的树中：

B C D

都是 A 的孩子。

第三部分：知识点复盘

• 二叉树中的右孩子，在还原时通常表示兄弟。
• 二叉树中的左孩子，在还原时表示第一个孩子。
• 根结点的右链表示森林中的多个根。

相关知识

• 科目导航：数据结构导航
• 阅读顺序：上一篇：二叉树的遍历 · 下一篇：树与二叉树的应用
• 关联专题：二叉树代码

18.5 本节复盘

三种存储方式

转换总口诀

左孩子，右兄弟

具体含义

遍历对应

易错点

• 双亲表示法的 parent 存的是数组下标，不是指针地址。
• 双亲表示法只有在已知结点下标时，找双亲才是 $O(1)$；找全部孩子通常是 $O(n)$。
• 森林可以用双亲表示法存储，只要多个根的 parent 都设为 -1。
• 孩子表示法存森林时，需要记录多个根的位置。
• 孩子兄弟表示法的两个指针虽然长得像二叉树指针，但含义不同。
• 树转二叉树时，兄弟要用右指针串起来。
• 遍历和转换都依赖固定的孩子次序；无序树必须先约定顺序。
• 任意二叉树都能解释为森林；根的右指针为空时才对应单棵树，非空时根的右链表示多个树根。