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

在数据结构的树型结构中森林与二叉树的转换是一个非常核心的知识点它不仅是树的存储、遍历的基础也是很多算法实现的关键。今天我们就从原理、步骤、实例三个维度彻底搞懂这个转换规则顺便把树转二叉树的前置知识也一起梳理清楚。一、先搞懂什么是森林什么是二叉树在正式讲转换前我们先明确两个基础概念树nn≥0个结点的有限集合有且仅有一个根结点其余结点分为 m 个互不相交的子树是一种一对多的非线性结构。森林mm≥0棵互不相交的树的集合。简单来说把一棵树的根结点删掉剩下的子树就构成了一片森林反过来给森林里的每棵树加一个共同的根就变成了一棵树。二叉树每个结点最多有两个子树左子树、右子树的树型结构是一种特殊的有序树。树 / 森林是一对多的结构而二叉树是最多一对二的结构转换的核心就是用二叉树的结构来存储树 / 森林把一对多的关系转化为一对二的关系方便计算机存储和操作。二、前置知识树转二叉树森林转二叉树的基础森林转二叉树的本质是先把森林里的每棵树都转成二叉树再把这些二叉树的根结点用右孩子的方式连接起来。所以我们先搞懂树转二叉树的规则这是后续所有转换的基础。树转二叉树的 3 步核心法则加线在所有兄弟结点之间加一条连线。去线对树中的每个结点只保留它与第一个孩子结点的连线删除它与其他孩子结点之间的连线。层次调整以根结点为轴将整棵树顺时针旋转一定角度让结构层次分明。关键规则第一个孩子是二叉树结点的左孩子兄弟转过来的孩子是结点的右孩子。实例演示原树的根是 AA 的孩子是 BB 的孩子是 E、CE 的孩子是 K、FK 的孩子是 LC 的孩子是 G、DD 的孩子是 HH 的孩子是 M、II 的孩子是 J。第一步加线给兄弟结点 B-C、K-F、G-D、M-I 等加线图中红线。第二步去线只保留每个结点和第一个孩子的连线删除其他孩子的连线。第三步旋转顺时针旋转后就得到了对应的二叉树完美符合 “左孩子是第一个孩子右孩子是兄弟” 的规则。三、核心森林转二叉树树转二叉树的延伸森林转二叉树本质是先把每棵树转成二叉树再把根结点依次作为右孩子连接步骤非常清晰。森林转二叉树的 4 步法则单树转二叉树把森林中的每一棵树都按照上面的「树转二叉树」规则转换成对应的二叉树。根结点连线将每棵二叉树的根结点从左到右依次用线连接起来后一个根作为前一个根的右孩子。层次调整以第一棵树的根为轴顺时针旋转整棵树形成最终的二叉树。核心规则左孩子是原树的第一个孩子右孩子是原树的下一个兄弟 / 下一棵树的根。四、逆操作二叉树转森林二叉树还原为森林有正转换就有逆转换二叉树转森林是把二叉树还原成多棵树的过程核心是 **“拆右孩子”**步骤如下二叉树转森林的 3 步法则拆右链从根结点开始若右孩子存在就把右孩子的连线删除再对删除后的右子树重复这个操作直到所有右孩子的连线都被删除得到多棵互不相交的二叉树。单二叉树转树把每一棵拆分出来的二叉树按照「二叉树转树」的规则还原成普通树。整理结构调整每棵树的层次得到最终的森林。二叉树转树的核心规则单棵二叉树还原为树对于二叉树中的每个结点它的左孩子是原树中该结点的第一个孩子它的左孩子的所有右子孙都是原树中该结点的兄弟孩子也就是该结点的其他孩子。操作步骤加线把结点的左孩子的所有右子孙都和该结点连接起来去线删除所有结点和其右孩子的连线层次调整还原成普通树。我们用一个二叉树还原森林的例子拆右链从根 A 开始A 的右孩子不存在所以第一棵二叉树是 A 为根的树拆分后得到 3 棵独立的二叉树A-B-C-D、E-F、G-H-I。单二叉树转树第一棵A 的左孩子是 BB 的右孩子是 CC 的右孩子是 D → 还原后 A 的孩子是 B、C、D第二棵E 的左孩子是 F → 还原后 E 的孩子是 F第三棵G 的左孩子是 HH 的右孩子是 I → 还原后 G 的孩子是 H、I。最终得到 3 棵树组成的森林和上图的最终结构完全一致。五、转换的核心本质与记忆口诀核心本质树 / 森林 → 二叉树把「兄弟关系」转化为「右孩子关系」把「父子关系」转化为「左孩子关系」用二叉树的结构存储一对多的树型关系。二叉树 → 树 / 森林把「右孩子关系」还原为「兄弟关系」把「左孩子关系」还原为「父子关系」拆分出多棵独立的树。超好用记忆口诀树转二叉树兄弟连右长子留左顺时针转。森林转二叉树每树转二叉根根右相连顺时针转。二叉树转树 / 森林右链全拆开左子当长子右子变兄弟。六、为什么要做这个转换很多同学会问好好的树 / 森林为什么要转成二叉树核心原因有 3 个存储方便二叉树的结构简单用数组、链表都能轻松存储而普通树的存储需要额外记录孩子的数量复杂度高。遍历统一二叉树有成熟的前序、中序、后序遍历算法树 / 森林转成二叉树后就可以用二叉树的遍历方法来实现树 / 森林的遍历。算法兼容很多树型算法比如哈夫曼树、平衡二叉树都是基于二叉树设计的转换后可以直接复用这些算法。七、常见易错点避坑❌ 混淆左右孩子左孩子一定是原树的第一个孩子右孩子一定是兄弟 / 下一棵树的根绝对不能搞反。❌ 树转二叉树时删除左孩子连线只能删除和非第一个孩子的连线必须保留和第一个孩子左孩子的连线。❌ 二叉树转森林时只拆根的右孩子必须递归拆分所有右孩子直到没有右孩子为止不能只拆一层。❌ 森林转二叉树时根的顺序错误森林中树的顺序决定了二叉树中根的右链顺序顺序不同转换后的二叉树也不同。