【数据结构】森林与二叉树的双向转换：原理、步骤与实例

在数据结构的树型结构中，森林与二叉树的转换是一个非常核心的知识点，它不仅是树的存储、遍历的基础，也是很多算法实现的关键。今天我们就从原理、步骤、实例三个维度，彻底搞懂这个转换规则，顺便把树转二叉树的前置知识也一起梳理清楚。

一、先搞懂：什么是森林？什么是二叉树？

在正式讲转换前，我们先明确两个基础概念：

• 树：n（n≥0）个结点的有限集合，有且仅有一个根结点，其余结点分为 m 个互不相交的子树，是一种一对多的非线性结构。
• 森林：m（m≥0）棵互不相交的树的集合。简单来说，把一棵树的根结点删掉，剩下的子树就构成了一片森林；反过来，给森林里的每棵树加一个共同的根，就变成了一棵树。
• 二叉树：每个结点最多有两个子树（左子树、右子树）的树型结构，是一种特殊的有序树。

树 / 森林是一对多的结构，而二叉树是最多一对二的结构，转换的核心就是用二叉树的结构来存储树 / 森林，把一对多的关系转化为一对二的关系，方便计算机存储和操作。

二、前置知识：树转二叉树（森林转二叉树的基础）

森林转二叉树的本质，是先把森林里的每棵树都转成二叉树，再把这些二叉树的根结点用右孩子的方式连接起来。所以我们先搞懂树转二叉树的规则，这是后续所有转换的基础。

树转二叉树的 3 步核心法则

1. 加线：在所有兄弟结点之间加一条连线。
2. 去线：对树中的每个结点，只保留它与第一个孩子结点的连线，删除它与其他孩子结点之间的连线。
3. 层次调整：以根结点为轴，将整棵树顺时针旋转一定角度，让结构层次分明。
   • 关键规则：第一个孩子是二叉树结点的左孩子，兄弟转过来的孩子是结点的右孩子。

实例演示

• 原树的根是 A，A 的孩子是 B；B 的孩子是 E、C；E 的孩子是 K、F；K 的孩子是 L；C 的孩子是 G、D；D 的孩子是 H；H 的孩子是 M、I；I 的孩子是 J。
• 第一步加线：给兄弟结点 B-C、K-F、G-D、M-I 等加线（图中红线）。
• 第二步去线：只保留每个结点和第一个孩子的连线，删除其他孩子的连线。
• 第三步旋转：顺时针旋转后，就得到了对应的二叉树，完美符合 “左孩子是第一个孩子，右孩子是兄弟” 的规则。

三、核心：森林转二叉树（树转二叉树的延伸）

森林转二叉树，本质是先把每棵树转成二叉树，再把根结点依次作为右孩子连接，步骤非常清晰。

森林转二叉树的 4 步法则

1. 单树转二叉树：把森林中的每一棵树都按照上面的「树转二叉树」规则，转换成对应的二叉树。
2. 根结点连线：将每棵二叉树的根结点，从左到右依次用线连接起来（后一个根作为前一个根的右孩子）。
3. 层次调整：以第一棵树的根为轴，顺时针旋转整棵树，形成最终的二叉树。
4. 核心规则：左孩子是原树的第一个孩子，右孩子是原树的下一个兄弟 / 下一棵树的根。

四、逆操作：二叉树转森林（二叉树还原为森林）

有正转换就有逆转换，二叉树转森林是把二叉树还原成多棵树的过程，核心是 **“拆右孩子”**，步骤如下：

二叉树转森林的 3 步法则

1. 拆右链：从根结点开始，若右孩子存在，就把右孩子的连线删除，再对删除后的右子树重复这个操作，直到所有右孩子的连线都被删除，得到多棵互不相交的二叉树。
2. 单二叉树转树：把每一棵拆分出来的二叉树，按照「二叉树转树」的规则还原成普通树。
3. 整理结构：调整每棵树的层次，得到最终的森林。

二叉树转树的核心规则（单棵二叉树还原为树）

• 对于二叉树中的每个结点：
  • 它的左孩子，是原树中该结点的第一个孩子；
  • 它的左孩子的所有右子孙，都是原树中该结点的兄弟孩子（也就是该结点的其他孩子）。
• 操作步骤：
  1. 加线：把结点的左孩子的所有右子孙，都和该结点连接起来；
  2. 去线：删除所有结点和其右孩子的连线；
  3. 层次调整，还原成普通树。

我们用一个二叉树还原森林的例子：

1. 拆右链：从根 A 开始，A 的右孩子不存在，所以第一棵二叉树是 A 为根的树；拆分后得到 3 棵独立的二叉树：A-B-C-D、E-F、G-H-I。
2. 单二叉树转树：
   • 第一棵：A 的左孩子是 B，B 的右孩子是 C，C 的右孩子是 D → 还原后 A 的孩子是 B、C、D；
   • 第二棵：E 的左孩子是 F → 还原后 E 的孩子是 F；
   • 第三棵：G 的左孩子是 H，H 的右孩子是 I → 还原后 G 的孩子是 H、I。

3. 最终得到 3 棵树组成的森林，和上图的最终结构完全一致。

五、转换的核心本质与记忆口诀

核心本质

• 树 / 森林 → 二叉树：把「兄弟关系」转化为「右孩子关系」，把「父子关系」转化为「左孩子关系」，用二叉树的结构存储一对多的树型关系。
• 二叉树 → 树 / 森林：把「右孩子关系」还原为「兄弟关系」，把「左孩子关系」还原为「父子关系」，拆分出多棵独立的树。

超好用记忆口诀

• 树转二叉树：兄弟连右，长子留左，顺时针转。
• 森林转二叉树：每树转二叉，根根右相连，顺时针转。
• 二叉树转树 / 森林：右链全拆开，左子当长子，右子变兄弟。

六、为什么要做这个转换？

很多同学会问：好好的树 / 森林，为什么要转成二叉树？核心原因有 3 个：

1. 存储方便：二叉树的结构简单，用数组、链表都能轻松存储，而普通树的存储需要额外记录孩子的数量，复杂度高。
2. 遍历统一：二叉树有成熟的前序、中序、后序遍历算法，树 / 森林转成二叉树后，就可以用二叉树的遍历方法来实现树 / 森林的遍历。
3. 算法兼容：很多树型算法（比如哈夫曼树、平衡二叉树）都是基于二叉树设计的，转换后可以直接复用这些算法。

七、常见易错点避坑

1. ❌ 混淆左右孩子：左孩子一定是原树的第一个孩子，右孩子一定是兄弟 / 下一棵树的根，绝对不能搞反。
2. ❌ 树转二叉树时删除左孩子连线：只能删除和非第一个孩子的连线，必须保留和第一个孩子（左孩子）的连线。
3. ❌ 二叉树转森林时只拆根的右孩子：必须递归拆分所有右孩子，直到没有右孩子为止，不能只拆一层。
4. ❌ 森林转二叉树时根的顺序错误：森林中树的顺序决定了二叉树中根的右链顺序，顺序不同，转换后的二叉树也不同。