Appearance
树与森林
一般树为什么需要单独讲
二叉树有一个隐藏的好处：每个结点最多两个孩子，所以可以用固定大小（lchild、rchild）的链结构表示。但一般的树——结点的度可能是 1、2、3、甚至几十——没法用固定大小的结构存储。
这一节解决两个问题：
- 一般树怎么存——三种主流存储方式（双亲表示法、孩子表示法、孩子兄弟表示法），各自的找双亲/找孩子代价不同
- 一般树和森林怎么遍历——以及它们与二叉树遍历的一一对应关系（408 综合题的高频考点）
"树与森林"这一块在 408 真题里非常稳定。2016-2026 这十一年里至少出现过 7 次，涵盖选择题（存储方式对比）、应用题（画孩子兄弟二叉树）和综合题（遍历对应）。
核心思想
| 概念 | 定义 |
|---|---|
| 一般树 | 每个结点孩子数不固定的树（区别于二叉树） |
| 森林 | m（m ≥ 0）棵互不相交的树的集合 |
| 空森林 | m = 0 时合法存在（空集也是森林） |
一般树有一条比二叉树更简单的"边数性质"：
因为除根外每个结点恰有一条入边。
操作详解
一、双亲表示法
思路：用一维数组存所有结点，每个结点带一个 parent 字段指向双亲在数组中的下标。
c
#define MAX_TREE_SIZE 100
typedef struct {
int data; // 数据域
int parent; // 双亲下标，根的 parent = -1
} PTNode;
typedef struct {
PTNode nodes[MAX_TREE_SIZE];
int n; // 当前结点数
} PTree;存储示例：
A
/ | \
B C D
/ \ |
E F G对应的双亲表示：
| 下标 | data | parent |
|---|---|---|
| 0 | A | -1 |
| 1 | B | 0 |
| 2 | C | 0 |
| 3 | D | 0 |
| 4 | E | 1 |
| 5 | F | 1 |
| 6 | G | 3 |
性能特点：
- 找双亲：O(1)——直接读 parent 字段
- 找孩子：O(n)——必须扫描整个数组，找哪些结点的 parent 是 i
- 找兄弟：O(n)——扫数组找 parent 相同的
典型应用：并查集（Union-Find）——并查集的核心操作就是"查双亲、合并集合"，正好契合双亲表示法。
二、孩子表示法
思路：每个结点单独维护一个孩子链表，链表里存所有孩子的下标。
c
typedef struct ChildNode {
int childIdx; // 孩子在数组中的下标
struct ChildNode *next; // 下一个孩子
} ChildNode;
typedef struct {
int data;
ChildNode *firstChild; // 指向该结点的孩子链表
} CTBox;
typedef struct {
CTBox nodes[MAX_TREE_SIZE];
int n, root; // 结点数和根的下标
} CTree;存储示例（同上一棵树）：
下标 data 孩子链表
0 A → [1] → [2] → [3] → ∧
1 B → [4] → [5] → ∧
2 C → ∧
3 D → [6] → ∧
4 E → ∧
5 F → ∧
6 G → ∧性能特点：
- 找孩子：O(度)——遍历当前结点的孩子链表
- 找双亲：O(n)——没有反向指针，只能扫描所有孩子链表
典型应用：以"自上而下"操作为主的场景，比如组织架构遍历、文件系统目录展开。
常见折中：把"孩子表示法 + parent 字段"结合起来，称为孩子双亲表示法，找双亲和找孩子都 O(度) 或 O(1)，代价是额外一个 parent 域。408 偶尔会提一句，但单独考的少。
三、孩子兄弟表示法
思路：每个结点只用两个指针——第一个孩子（firstChild）和右兄弟（nextSibling）。
c
typedef struct CSNode {
int data;
struct CSNode *firstChild; // 第一个孩子
struct CSNode *nextSibling; // 右兄弟（同一双亲下的下一个孩子）
} CSNode, *CSTree;存储示例：
原一般树 孩子兄弟表示（二叉链表形态）
A A
/ | \ |
B C D B ─ C ─ D
/ \ | | |
E F G E ─ F G
把 firstChild 当作左指针、nextSibling 当作右指针，整个树形态就和"一棵二叉树"一致了。关键洞察：孩子兄弟表示法把一般树映射成了一棵二叉树。这就是为什么"树/森林 ↔ 二叉树"的转换可以自然完成。
性能特点：
- 找第一个孩子：O(1)
- 找指定孩子（第 k 个）：O(k)——沿 nextSibling 链走 k - 1 步
- 找双亲：不方便（除非额外加 parent 指针），但配合栈/递归回溯没问题
- 空间利用率高——每个结点固定两个指针，结构规整
典型应用：树 ↔ 二叉树转换、Lisp 等以"二叉结构表示一般树"的语言、xml/json 的内部树表示。
详细的转换规则见 树与森林和二叉树的转换。
四、三种存储方式对比
| 存储方式 | 找双亲 | 找孩子 | 空间开销 | 适用场景 |
|---|---|---|---|---|
| 双亲表示法 | O(1) | O(n) | 1 个 parent 域 | 并查集、查双亲为主 |
| 孩子表示法 | O(n) | O(度) | 孩子链表开销 | 查孩子为主、目录展开 |
| 孩子兄弟表示法 | 不方便 | 第一个孩子 O(1)、第 k 个 O(k) | 固定 2 个指针 | 树↔二叉树转换、形态规整 |
408 选择题套路：题目会描述一个使用场景（例如"频繁查找某结点的所有后代"），让你选择哪种存储方式最合适。答题思路：先判定主要操作是"找双亲"还是"找孩子"，再看题目是否暗示需要"转换为二叉树处理"。
五、树的遍历
一般树（非二叉树）的遍历有三种：
| 遍历方式 | 规则 | 与二叉树遍历的对应 |
|---|---|---|
| 先根遍历 | 先访问根，再依次先根遍历每棵子树 | 对应转换后二叉树的先序遍历 |
| 后根遍历 | 先依次后根遍历每棵子树，再访问根 | 对应转换后二叉树的中序遍历 |
| 层次遍历 | 按层从上到下、每层从左到右（用队列实现） | 没有严格对应 |
没有中根遍历——一般树的孩子数不固定，"在哪个孩子之前访问根"没法定义。这是和二叉树最大的差别之一。
示例（同前述树）：
A
/ | \
B C D
/ \ |
E F G- 先根遍历：A B E F C D G
- 后根遍历：E F B C G D A
- 层次遍历：A B C D E F G
六、森林的遍历
森林由若干棵树组成，遍历森林时按"森林是一棵棵树的有序集合"处理：
| 遍历方式 | 规则 | 与二叉树遍历的对应 |
|---|---|---|
| 先序遍历森林 | 访问第一棵树的根 → 先序遍历第一棵树的子树森林 → 先序遍历其余树构成的森林 | 对应转换后二叉树的先序遍历 |
| 中序遍历森林 | 中序遍历第一棵树的子树森林 → 访问第一棵树的根 → 中序遍历其余树构成的森林 | 对应转换后二叉树的中序遍历 |
没有后序遍历森林——大纲只列了先序和中序两种。可以理解为森林被转换成二叉树后只关心这两个对应关系。
七、树/森林/二叉树遍历对应表（综合题核心）
这张表是 408 综合题的直接得分点：
| 树（一般树）的遍历 | 森林的遍历 | 对应二叉树的遍历 |
|---|---|---|
| 先根遍历 | 先序遍历 | 先序遍历 |
| 后根遍历 | 中序遍历 | 中序遍历 |
应用题套路：题目给你一棵一般树或一片森林，要求"将其转换为二叉树后给出先序/中序遍历序列"。两种走法都行：
- 走法 A：先把树/森林按孩子兄弟法转成二叉树（画图），再做二叉树的先序/中序
- 走法 B：直接对原树/森林做先根/后根（或先序/中序）遍历——结果完全相同
走法 B 在熟练后更快，因为不用画转换图。
复杂度分析
| 操作 | 复杂度 |
|---|---|
| 建立 n 个结点的一般树（任一存储方式） | O(n) |
| 树/森林的先根、后根、层次遍历 | O(n) |
| 双亲表示法查双亲 | O(1) |
| 孩子表示法查孩子 | O(度) |
考研高频考点
- ⭐ 三种存储方式的特点对比——给定使用场景选合适的存储方式（选择题年年考）
- ⭐ 孩子兄弟表示法 ↔ 二叉树的对应关系——给一棵树画其对应的二叉链表（应用题高频）
- ⭐ 树/森林/二叉树遍历的对应——综合题往往让你写出三者的遍历序列并验证一致性
- ⭐ 结点数与边数的关系：n 结点的树有 n - 1 条边
- 双亲表示法的实际实现（并查集的基础）
- 一般树没有"中根遍历"、森林没有"后序遍历"（概念辨析易错）
- 度的概念在一般树中的应用（区分"树的度"和"结点的度"）
易错：森林的中序遍历不是"按二叉树中序的递归方式直接套到森林上"，而是"中序遍历第一棵树的子树森林 → 访问第一棵树的根 → 中序遍历其余树"。注意"访问根"这一步发生的时机。
易错：把一般树转换成二叉树后，根没有右子树（除非原来是一片森林）。这是判断题里常用来诈分的点——某些复习材料会用"任意二叉树都可以反过来对应一片森林"来表述，但只有满足"根没有右孩子"的二叉树对应一棵单独的树，根有右孩子的二叉树对应的是森林。
相关知识
- 树与二叉树基本概念：本文聚焦"一般树"，那篇文章聚焦"二叉树"，两者互补
- 树与森林和二叉树的转换：基于孩子兄弟表示法的具体转换规则
- 并查集：双亲表示法的典型应用
- 哈夫曼树：本身是二叉树，但其构造过程用到了"森林合并"的语义
- 先序遍历、中序遍历：二叉树遍历，与树/森林遍历存在一一对应