在现实生活和计算机系统中，多叉树（如文件系统的目录树、企业组织架构图、XML/JSON 语法树）与森林（多个独立树的集合）更为普遍。多叉树的节点度数各不相同，直接为每个节点预留最大可能的孩子指针数组不仅极其浪费内存，而且操作逻辑非常繁杂。

二叉树由于每个节点固定只有两个有序槽位（左、右），具有极其紧凑和高效的存储与算法实现。

那么，能否将任意形态的多叉树甚至由多棵树构成的森林，完全等价地转换为一棵二叉树？

答案正是孩子兄弟表示法（Left-Child Right-Sibling, LCRS）。通过这一表示法，许多本来只针对标准二叉树的高效算法就可以应用到多叉树与森林中，替代那些繁杂的操作。

---

学习目标

完成本节后，你应该能够：

• 掌握树转换为二叉树的“加线、抹线、旋转”几何法则与本质原理；
• 解释为什么由单棵树转换得到的二叉树，其根节点的右孩子必定为空；
• 熟练完成森林与二叉树之间的相互可逆转换（双向映射）；
• 区分树的先根遍历、后根遍历与森林的先序、后序遍历规则，理解树为什么没有“中根遍历”；
• 严格推导并牢记树/森林遍历与二叉树遍历的等价映射定理（尤其是“后根遍历 $⟺$ 二叉树中序遍历”的深层原因）。

---

4.5.1 树与二叉树的转换

1. 转换的底层语义：左孩子，右兄弟

我们在 4.1 节介绍过孩子兄弟链表：

• firstChild（左指针）：指向该节点的第一个孩子（长子）；
• nextSibling（右指针）：指向该节点的下一个相邻右侧兄弟。

当我们将 firstChild 当作二叉树的 left，将 nextSibling 当作二叉树的 right 时，一般多叉树就自然转换为了一棵二叉树。

2. 树转二叉树的直观几何规则（三步法）

1. 加线：在所有属于同一个父节点的兄弟节点之间，画一条水平连线；
2. 抹线：对树中的每一个节点，只保留它与**第一个孩子节点（最左孩子）**的连线，抹去它与其他所有孩子节点的连线；
3. 旋转平移：以根节点为轴心，顺时针旋转 ${45}^{\circ }$。原来的长子成为左孩子，原来的水平兄弟链成为右斜向下的右孩子链。

PROP性质 · 单树转换二叉树的根右链为空

由任意一棵单棵树转换得到的二叉树，其根节点的右子树一定为空（root->right == nullptr）。 原因：树的根节点是全局唯一的，它在逻辑上没有任何兄弟节点，因此其 nextSibling 必定为空。

---

4.5.2 森林与二叉树的转换

森林（forest）是 $m$（$m\ge 0$）棵互不相交的树的集合：

$$F=(T_1,T_2,\dots ,T_m).$$

当 $m=0$ 时，为空森林；当 $m=1$ 时，森林退化为单棵树。

1. 森林转换为二叉树

既然单棵树的根节点没有兄弟，那么如果有多棵树，我们就可以将第二棵树 $T_2$ 的根节点看作第一棵树 $T_1$ 根节点的“兄弟”，挂在 $T_1$ 的右指针上；将第三棵树 $T_3$ 的根节点挂在 $T_2$ 根节点的右指针上，依此类推。

森林转二叉树转换算法：

1. 将森林中的每一棵树 $T_1,T_2,\dots ,T_m$ 分别按照 4.5.1 节规则转换为对应的二叉树 $B_1,B_2,\dots ,B_m$；
2. 第一棵二叉树 $B_1$ 的根节点直接作为整棵二叉树的根；
3. 从 $B_2$ 开始，依次将后一棵二叉树的根节点，作为前一棵二叉树根节点的**右孩子（right）**连接起来。

2. 二叉树还原为森林

二叉树转换为森林是上述过程的完全逆过程：

1. 切断右链：从二叉树的根节点开始，沿着根的右孩子指针一路向下，将所有右指针连线全部断开，得到 $m$ 棵独立的二叉树 $B_1,B_2,\dots ,B_m$；
2. 独立还原：对每一棵二叉树 $B_i$，按逆向规则还原为单棵多叉树 $T_i$；
3. 组合森林：将还原出的所有树集合起来，即得到原始森林 $F=(T_1,T_2,\dots ,T_m)$。

THM定理 1 · 森林与二叉树的双射同构

森林与二叉树之间存在**一一对应（Bijective Mapping）**关系。任意给定的森林都可以唯一转换得到一棵二叉树，任意二叉树也可以唯一还原为原始森林。

---

4.5.3 树与森林的遍历及对应关系

1. 树的遍历规则

对于一棵非空的一般多叉树，有两种自然的深度优先遍历策略：

• 先根遍历（Pre-order Tree Traversal）：
  1. 先访问根节点；
  2. 从左到右，依次先根遍历根节点的每一棵子树。
• 后根遍历（Post-order Tree Traversal）：
  1. 从左到右，依次后根遍历根节点的每一棵子树；
  2. 最后访问根节点。

WARN易错点 · 为什么一般树没有“中根遍历”？

二叉树有严格的“左子树”与“右子树”，根节点正好位于中间（$L\to D\to R$）。但在一般多叉树中，一个节点可能拥有 $3$ 个或更多的孩子（如 $B,C,D$），无法唯一定义哪个孩子是“左”，哪个孩子是“中间”，因此一般树只有先根遍历和后根遍历，不存在中根遍历。

2. 森林的遍历规则

设森林 $F=(T_1,T_2,\dots ,T_m)$，其中 $T_1$ 的根为 $R_1$，其子树构成的子森林为 $F_1$：

• 先序遍历森林（Pre-order Forest Traversal）：
  1. 访问第一棵树的根节点 $R_1$；
  2. 先序遍历第一棵树中根节点的子树森林 $F_1$；
  3. 先序遍历除了第一棵树之后剩余的树构成的森林 $(T_2,\dots ,T_m)$。
• 后序遍历森林（Post-order Forest Traversal）：
  1. 后序遍历第一棵树中根节点的子树森林 $F_1$；
  2. 访问第一棵树的根节点 $R_1$；
  3. 后序遍历除了第一棵树之后剩余的树构成的森林 $(T_2,\dots ,T_m)$。

---

3. 核心定理：树/森林遍历与二叉树遍历的等价对应

这是树形结构理论与各类算法考试中最核心、最常考的对应关系：

THM定理 2 · 遍历对应等价定理

原始结构	原始遍历方式	对应转换后二叉树的遍历方式
树（Tree）	先根遍历	二叉树的前序遍历（$DLR$）
树（Tree）	后根遍历	二叉树的中序遍历（$LDR$） ⚠️
森林（Forest）	先序遍历	二叉树的前序遍历（$DLR$）
森林（Forest）	后序遍历	二叉树的中序遍历（$LDR$） ⚠️

PROOF为什么“树的后根遍历”对应“二叉树的中序遍历”而非后序遍历？

请观察树转二叉树后的左右子树含义：

• 二叉树的左子树：对应原树根节点的所有后代孩子（子树森林）；
• 二叉树的根节点：对应原树的根节点自身；
• 二叉树的右子树：对应原树根节点的后续兄弟。

现在我们看树的后根遍历：

1. 先遍历所有子树孩子（即二叉树的左子树）；
2. 再访问本根节点（即二叉树的根节点）。

这在二叉树的执行序列中恰好是：先左子树 $\to$ 再根节点（即二叉树的 $LDR$ 中序遍历）！

而在二叉树的**后序遍历（$LRD$）**中，右子树（后续兄弟）必须在根节点之前被访问，这与树的后根逻辑完全不符。因此：树/森林的后根/后序遍历，严格等价于对应二叉树的中序遍历。

---

小结与自测

树与森林通过==孩子兄弟二叉链表（左孩子、右兄弟）==与二叉树建立了严密的双射同构关系。森林多根串联于右链，树的先根映射二叉树前序，树的后根深刻映射为二叉树的中序。

请尝试回答以下自测问题：

1. 一棵含有 $n$ 个节点的一般树转换成二叉树后，这棵二叉树的根节点的左指针与右指针分别有什么特点？
2. 已知某森林包含 3 棵树，节点总数分别为 $n_1,n_2,n_3$。转换为二叉树后，二叉树根节点的右子树包含多少个节点？
3. 为什么一般多叉树不能定义中根遍历？
4. 给定一棵多叉树，其先根遍历序列为 A B C D E，后根遍历序列为 B D E C A。请画出该多叉树转换为二叉树后的中序遍历序列。
5. 简述在文件系统或组织架构等多叉树系统中，采用孩子兄弟二叉链表代替指针数组的主要工程优势。

下一节进入4.6 二叉树的经典问题：我们将综合运用递归框架、DFS/BFS 状态转移与树形动态规划，系统突破二叉树形态统计、路径回溯、对称变换与最近公共祖先等殿堂级经典算法问题。