树、森林与二叉树的转换
这一节的全部内容可以压成一句话：「左孩子右兄弟」把任意树变成二叉树，于是树的遍历也就变成了二叉树的遍历。
考法只有三种：画转换、由遍历序列反推、判断遍历序列的对应关系。最后一种是选择题，前两种是综合题。
机制
三种存储结构
1. 双亲表示法：采用一组连续空间来存储每个结点，同时在每个结点中增设一个伪指针，指示其双亲结点在数组中的位置。根结点下标为 0，其伪指针域为 −1。
#define MAX_TREE_SIZE 100
typedef struct{
ElemType data; //数据元素
int parent; //双亲位置域
}PTNode;
typedef struct{
PTNode nodes[MAX_TREE_SIZE]; //双亲表示
int n; //结点数
}PTree;双亲表示法利用了每个结点（根结点除外）只有唯一双亲的性质，可以很快地得到每个结点的双亲结点，但求结点的孩子时则需要遍历整个结构。
2. 孩子表示法：把每个结点的孩子结点排列起来，视为一个线性表，以单链表作存储结构。找孩子快，找双亲慢——正好与双亲表示法互补。
3. 孩子兄弟表示法：又称二叉树表示法，以二叉链表作为树的存储结构。每个结点包含三部分：结点值、指向结点第一个孩子结点的指针 fch、指向结点下一个兄弟结点的指针 nsib。
typedef struct node{
ElemType data; //数据域
struct node *fch,*nsib; //孩子与兄弟域
}*Tree;孩子兄弟表示法就是「树转换成二叉树」这件事的存储形式——下面 5.4.2 讲的转换规则，讲的正是这个结构。
关联对照：
教材 5.5.2 的 并查集 用的正是双亲表示法： 「通常用树的双亲表示作为并查集的存储结构。」 因为并查集只需要
Find（一路向上找根），根本不需要找孩子——双亲表示法的短板在这里完全不构成问题。
树转换为二叉树：左孩子右兄弟
规则：每个结点的左指针指向它的第一个孩子，右指针指向它在树中的相邻右兄弟，这个规则也称左孩子右兄弟。
根结点没有兄弟，因此树转换得到的二叉树没有右子树。
画法三步：
- 在兄弟结点之间加一连线；
- 对每个结点，只保留它与第一个孩子的连线，而与其他孩子的连线全部抹掉；
- 以树根为轴心，顺时针旋转 45°。
flowchart LR subgraph T["原树"] A1(("A")) --- B1(("B")) A1 --- C1(("C")) A1 --- D1(("D")) B1 --- E1(("E")) B1 --- F1(("F")) D1 --- G1(("G")) end subgraph B["转换后的二叉树"] A2(("A")) --- B2(("B")) B2 --- E2(("E")) B2 --- C2(("C")) E2 --- F2(("F")) C2 --- D2(("D")) D2 --- G2(("G")) end T ==>|"左孩子右兄弟<br/>A 无右子树"| B classDef t fill:#e3f2fd,stroke:#1565c0 classDef b fill:#c8e6c9,stroke:#1b5e20 class A1,B1,C1,D1,E1,F1,G1 t class A2,B2,C2,D2,E2,F2,G2 b
（对应教材图 5.22。注意
森林转换为二叉树
规则与树类似。先将森林中的每棵树转换为二叉树，由于任意一棵树对应的二叉树的右子树必空，森林中各棵树的根也可视为兄弟关系，将第二棵树对应的二叉树当作第一棵二叉树根的右子树……以此类推。
画法三步：
- 将森林中的每棵树转换成相应的二叉树；
- 每棵树的根也可视为兄弟关系，在每棵树的根之间加一根连线；
- 以第一棵树的根为轴心顺时针旋转 45°。
或者先在森林中每棵树的根之间加一根连线，然后再采用树转换为二叉树的方法。
二叉树转换为森林
规则：若二叉树非空，则二叉树的根及其左子树为第一棵树的二叉树形式，所以将根的右链断开。二叉树根的右子树又可视为一个由除第一棵树外的森林转换后的二叉树，应用同样的方法，直到最后只剩一棵没有右子树的二叉树为止，最后将每棵二叉树依次转换成树，就得到了原森林。
二叉树转换为树或森林是唯一的。
边界辨析：
「树 → 二叉树」和「二叉树 → 森林」都是唯一的，但它们不是一一对应。 一棵没有右子树的二叉树才对应一棵树；有右子树的二叉树对应的是一个森林。 所以题目给一棵二叉树问「对应的树有几个结点」时，先看根有没有右孩子——有就说明这是森林不是树。
树与森林的遍历
树的遍历有两种主要方式：
| 遍历 | 规则 | 对应二叉树的 |
|---|---|---|
| 先根遍历 | 先访问根结点，再依次遍历根结点的每棵子树（遍历子树时仍遵循先根后子树的规则） | 先序序列 |
| 后根遍历 | 先依次遍历根结点的每棵子树（遍历子树时仍遵循先子树后根的规则），再访问根结点 | 中序序列 |
另外，树也有层次遍历，与二叉树的层次遍历思想基本相同。
森林的遍历也有两种：
| 遍历 | 规则 | 对应二叉树的 |
|---|---|---|
| 先序遍历森林 | 访问第一棵树的根 → 先序遍历第一棵树中根结点的子树森林 → 先序遍历除去第一棵树之后剩余的树构成的森林 | 先序序列 |
| 中序遍历森林 | 中序遍历第一棵树中根结点的子树森林 → 访问第一棵树的根 → 中序遍历除去第一棵树之后剩余的树构成的森林 | 中序序列 |
教材的例子：图 5.22 的树，先根遍历序列为
层次辨析：
树 / 森林没有「后序遍历」，只有「后根 / 中序」。 因为转换后的二叉树里，「树的根」跑到了左子树的上方、右兄弟的左边—— 走完子树再访问根，在二叉树上看正好是中序的位置，不是后序。 凡是看到「树的后根遍历对应二叉树的后序遍历」，直接判错。
手算模板
树 → 二叉树：兄弟连线 → 只留第一个孩子的连线 → 顺时针转 45°。检验：根一定没有右孩子。
森林 → 二叉树：各树根之间连线 → 按上面走。检验：根有右孩子。
二叉树 → 森林：沿根的右链一路断开，断出几段就是几棵树；每段再按「左孩子是长子、右链是兄弟」还原。
由遍历序列反推：把树 / 森林的遍历翻译成二叉树的遍历（先根↔先序、后根↔中序）， 然后用 5.3.1 的「先序 + 中序」方法还原二叉树，最后再转回树 / 森林。 这是 2020、2021 综合题的标准路线。
边界
| 说法 | 判断 | 说明 |
|---|---|---|
| 「双亲表示法找孩子很快」 | ❌ | 求孩子时需要遍历整个结构；它快的是找双亲 |
| 「树转换的二叉树可能有右子树」 | ❌ | 根结点没有兄弟，所以没有右子树 |
| 「有右子树的二叉树对应一棵树」 | ❌ | 对应的是森林 |
| 「二叉树转换为树的结果不唯一」 | ❌ | 唯一 |
| 「树的后根遍历对应二叉树的后序遍历」 | ❌ | 对应中序 |
| 「森林的中序遍历对应二叉树的后序遍历」 | ❌ | 对应中序 |
| 「树有先序、中序、后序三种遍历」 | ❌ | 树只有先根、后根（加层次）；森林只有先序、中序 |
| 「孩子兄弟表示法是三叉链表」 | ❌ | 是二叉链表：fch + nsib |
| 「森林至少两棵树」 | ❌ |
口径差异：
算竞里存树一律用邻接表 / vector 存儿子，
fa[]数组当双亲——即「孩子表示法 + 双亲表示法」混用， 从不用「孩子兄弟表示法」，因为它只是为了省指针，而算竞不缺内存。 所以「左孩子右兄弟」这个转换在算竞视角里是多余的，但 408 把它当成第 5 章的枢纽： 树和森林的所有遍历定义都是靠它借二叉树来定义的。 不接受这个前提，5.4.3 的对应关系只能死背。
对照速查
| 存储结构 | 找双亲 | 找孩子 | 本质 |
|---|---|---|---|
| 双亲表示法 | 快 | 慢（遍历全表） | 数组 + parent 伪指针，根为 −1 |
| 孩子表示法 | 慢 | 快 | 数组 + 孩子单链表 |
| 孩子兄弟表示法 | 慢 | 较快 | 二叉链表，fch + nsib |
| 树 / 森林 | 对应二叉树 |
|---|---|
| 树的先根遍历 | 先序 |
| 树的后根遍历 | 中序 |
| 森林的先序遍历 | 先序 |
| 森林的中序遍历 | 中序 |
| 转换 | 检验标志 |
|---|---|
| 树 → 二叉树 | 根没有右孩子 |
| 森林 → 二叉树 | 根有右孩子（除非只有一棵树） |
| 二叉树 → 森林 | 沿根的右链断开，段数 = 树的棵数 |
考点
- 左孩子右兄弟规则及「树转换的二叉树没有右子树」（2009、2011 命题追踪）。
- 森林与二叉树的转换（2014 命题追踪）。
- 由遍历序列构造二叉树并转换为对应的森林（2020、2021 命题追踪）——综合题主力。
- 四条遍历对应关系（2019、2020 命题追踪），尤其「后根 ↔ 中序」。
- 三种存储结构各自的强弱，以及并查集为什么选双亲表示法。
链接
- 🏠 返回总览：数据结构第 5 章：树与二叉树总览
- ⬅️ 上一节：5.3.2 线索二叉树
- ➡️ 下一节：5.5 树与二叉树的应用
- 🔗 森林与树只差一个根：5.1.2 基本术语
- 🔗 由序列还原二叉树：5.3.1 二叉树的遍历
- 🔗 双亲表示法的用武之地：5.5.2 并查集
- 📖 名词库：第 5 章名词库