Appearance
树与森林 ↔ 二叉树的转换
为什么需要树与森林 ↔ 二叉树的转换
树和森林的结构形态多样，每个结点的孩子数量不固定，存储和操作都不方便。而二叉树结构规整，每个结点最多两个孩子，已有大量成熟算法。因此，将树或森林转换为二叉树来处理，是数据结构中的经典思路。
408 考研中，树、森林与二叉树之间的相互转换及其遍历对应关系是必考内容，常以选择题和综合应用题形式出现。
核心思想
转换的理论基础是孩子兄弟表示法（又称二叉链表表示法）：
- 左指针指向该结点的第一个孩子
- 右指针指向该结点的下一个右兄弟
孩子兄弟表示法结点结构：
┌──────────┬──────┬──────────────┐
│ firstChild│ data │ nextSibling │
└──────────┴──────┴──────────────┘
↓ ↓
第一个孩子 下一个右兄弟这样，任意一棵树都可以用一棵二叉树来唯一表示，左孩子 = 第一个孩子，右孩子 = 下一个兄弟。
树与森林转换流程图
交互可视化
通过下方的交互动画，你可以逐步观察树与森林 ↔ 二叉树的转换的执行过程：
操作详解
树转二叉树
将一棵普通树转换为二叉树，口诀："兄弟相连留长子"。
关键步骤：
- 在所有相邻兄弟结点之间加一条连线
- 对每个结点，只保留它与第一个孩子的连线，删除与其他孩子的连线
- 以根结点为轴心，将整棵树顺时针旋转 45° 调整形态
转换特点：
- 树的根结点转换后没有右子树（因为根没有兄弟）
- 转换是唯一的，即一棵树对应唯一一棵二叉树
森林转二叉树
森林是 m 棵互不相交的树的集合。转换方法：
关键步骤：
- 将森林中每棵树各自转换为二叉树
- 将第二棵二叉树作为第一棵二叉树根结点的右子树
- 将第三棵二叉树作为第二棵二叉树根结点的右子树
- 依此类推，所有树的根结点通过右指针相连
等价理解：把森林中各棵树的根看作兄弟关系，然后整体按"孩子兄弟表示法"处理即可。
二叉树还原
二叉树转树
关键步骤：
- 若某结点 p 是其双亲的左孩子，则将 p 的右孩子、右孩子的右孩子……都与 p 的双亲用线连接
- 删除原二叉树中所有结点与其右孩子的连线
- 调整层次，使之成为一棵树
二叉树转森林
判断依据：若二叉树的根结点有右子树，则可转为森林；否则只能转为一棵树。
关键步骤：
- 从根结点开始，沿右指针断开，得到若干棵二叉树（根、根的右子树、根的右子树的右子树……）
- 将每棵二叉树分别转换为树
- 所有树构成森林
遍历对应关系
树、森林与二叉树的遍历之间存在严格的对应关系，这是 408 考研的核心考点。
树的遍历对应
| 树的遍历 | 对应的二叉树遍历 | 说明 |
|---|---|---|
| 先根遍历 | 先序遍历 | 根→第一个孩子对应根→左子树 |
| 后根遍历 | 中序遍历 | 最后访问根对应中序访问根 |
森林的遍历对应
| 森林的遍历 | 对应的二叉树遍历 | 说明 |
|---|---|---|
| 先序遍历 | 先序遍历 | 依次先根遍历每棵树 |
| 中序遍历 | 中序遍历 | 依次后根遍历每棵树 |
注意：森林没有"后序遍历"的说法，森林的中序遍历也称为森林的后根遍历。
复杂度分析
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| 树转二叉树 | O(n) | 每个结点处理一次 |
| 森林转二叉树 | O(n) | n 为森林中所有结点总数 |
| 二叉树转树 | O(n) | 每个结点处理一次 |
| 二叉树转森林 | O(n) | 每个结点处理一次 |
空间复杂度：O(1)，转换过程仅修改指针，不需要额外存储空间（递归实现时栈空间为 O(h)，h 为树高）。
考研高频考点
- ⭐ 树的先根遍历 = 二叉树的先序遍历，树的后根遍历 = 二叉树的中序遍历（选择题高频）
- ⭐ 森林的先序遍历 = 二叉树的先序遍历，森林的中序遍历 = 二叉树的中序遍历（选择题高频）
- ⭐ 给定树/森林画出对应的二叉树，或由二叉树还原树/森林（应用题必考）
- ⭐ 判断二叉树能还原为树还是森林（根结点是否有右子树）
- 孩子兄弟表示法的结点结构及含义（概念题）
- 含 n 个结点的森林转二叉树后，二叉树中空指针域的个数分析（偶尔考）