【数据结构】树、森林与二叉树的转换（含详细图解）

【数据结构】树、森林与二叉树的转换（含详细图解）

引用

CSDN

1.

https://blog.csdn.net/2301_82213854/article/details/143219756

前言

在数据结构的世界里，树、森林和二叉树是重要的概念，它们之间存在着巧妙的转换关系，这种转换不仅具有理论意义，更在实际的算法设计和数据处理中有着广泛的应用。

树转换为二叉树

转换步骤详解

1. 连接兄弟节点
2. 给除长子（第一个左孩子）以外的孩子去线
3. 层次调整

图例解释：

例如我们有下面一课树：

（一）连接兄弟节点

1. 目的与作用：在树结构中，每个节点可能有多个孩子节点。通过连接兄弟节点，可以将树中的兄弟关系转化为二叉树中的右指针关系。这样，在二叉树中，一个节点的右孩子就代表了它在原树中的兄弟节点。
2. 具体操作：对于树中的每个节点，除了其第一个孩子节点（长子）外，将其余孩子节点依次连接成一个链表。这个链表的头指针指向该节点的第一个孩子，链表中的每个节点（即原树中的节点）的右指针指向其下一个兄弟节点。

首先，我们将每一个兄弟连接：

（二）给除长子以外的孩子去线

1. 目的与作用：在树转换为二叉树的过程中，为了明确二叉树中节点的父子关系，需要去除除长子以外的孩子与父节点之间的直接连接。这样，在二叉树中，一个节点的左孩子就代表了它在原树中的长子。
2. 具体操作：在完成兄弟节点的连接后，将原树中除长子以外的孩子节点与父节点之间的连接断开。

然后，给除长子（第一个左孩子）以外的孩子去线：

（三）层次调整

1. 目的与作用：经过前面两个步骤的操作，树的结构已经初步转化为二叉树的形式。但是，还需要进行一些调整，以确保二叉树的结构正确。层次调整主要是针对树的根节点和一些特殊情况进行处理，使得转换后的二叉树符合二叉树的定义和规范。
2. 具体操作：树的根节点没有兄弟，所以其右指针设为空。对于其他节点，如果在转换过程中出现了不合理的连接或者指针指向错误的情况，需要进行相应的调整。

最后，层次调整：

需要根据二叉树的定义进行调整，确保左孩子是长子，右孩子是兄弟节点。

森林转换为二叉树

转换步骤详解

1. 将森林里的每一颗树转换为二叉树
2. 将所有二叉树转换为一颗二叉树

图例解释：

例如我们有下面的森林：

（一）将森林里的每一棵树转换为二叉树

1. 转换原理：森林是由多棵树组成的集合，而每一棵树都可以独立地按照树转换为二叉树的方法进行转换。这个过程与单独将一棵树转换为二叉树的原理相同，都是通过重新组织节点之间的连接关系，使得树的结构能够在二叉树的框架下得以合理表示。
2. 具体操作：首先，将森林里的每一颗树转换为二叉树：

（二）将所有二叉树转换为一棵二叉树

1. 连接规则：在将森林中的每一棵树都转换为二叉树之后，需要将这些二叉树连接起来，形成一棵更大的二叉树，从而将森林的结构整合到一个统一的二叉树结构中。
2. 具体操作：

• 把第一棵树的根节点作为转换后的二叉树的根节点。（即第一颗树不做任何操作，直接抄下来）
• 将第二棵树的根节点作为第一棵二叉树根节点的右孩子。
• 将第三棵树的根节点作为第二棵二叉树根节点（即第二棵树转换后的二叉树根节点在新二叉树中的位置）的右孩子，以此类推。

然后，将所有二叉树转换为一颗二叉树：

二叉树转换成树

（确实就是树转换为二叉树的逆过程）

转换步骤详解

1. 给除长子（第一个左孩子）以外的孩子加线
2. 去除与右孩子的连线
3. 层次调整

图例解释：

例如我们有下面的二叉树：

（一）加线

1. 目的与作用：在二叉树中，一个节点的左孩子代表了它在原树中的长子，右孩子代表了它在原树中的兄弟。加线的目的是为了恢复原树中节点之间的父子关系和兄弟关系。通过加线，可以将二叉树中的兄弟关系重新连接为原树中的父子关系。
2. 具体操作：对于二叉树中的每个节点，如果它有右孩子，就在它的右孩子和它的父节点之间添加一条连线。这条连线表示在原树中，这个右孩子节点是该节点的兄弟节点的孩子。

首先，我们给除长子（第一个左孩子）以外的孩子加线：

（二）去线

1. 目的与作用：去线的目的是去除在二叉树转换过程中产生的多余连线，以恢复原树的结构。在二叉树中，节点的左孩子和右孩子之间的连线是为了表示二叉树的结构关系，但在原树中并不存在这样的关系。通过去线，可以去除这些多余的连线，使树的结构更加清晰。
2. 具体操作：将二叉树中所有节点与其左孩子之间的连线保留，去除其他所有连线。这些保留的连线代表了原树中节点之间的父子关系。

然后，我们去除与右孩子的连线：

（三）层次调整

1. 目的与作用：经过加线和去线操作后，树的结构已经初步恢复，但可能还存在一些不合理的层次关系。层次调整的目的是进一步调整树的层次结构，使其符合原树的结构特点。
2. 具体操作：根据原树的层次结构，对转换后的树进行层次调整。这可能涉及到调整节点的位置、重新排列节点等操作。

最后，我们进行层次调整：

将二叉树转换成森林

转换步骤详解

1. 寻找右孩子去线
2. 将分离的二叉树转换成树

（一）寻找右孩子去线

1. 目的与作用：在二叉树中，根节点的右孩子以及右孩子的后代可以看作是森林中的一棵树。通过寻找右孩子并去线，可以将二叉树逐步分离成多个子二叉树，每个子二叉树对应森林中的一棵树。
2. 具体操作：从二叉树的根节点开始，寻找根节点的右孩子。如果根节点有右孩子，就将根节点与右孩子之间的连线断开。然后，对右孩子为根的子二叉树继续进行相同的操作，直到没有右孩子为止。

首先，我们寻找右孩子去线：

（二）将分离的二叉树转换成树

1. 转换原理：经过上一步的操作，二叉树已经被分离成多个子二叉树。这些子二叉树可以看作是森林中的一棵棵树，需要将它们转换回树的结构。这个过程与二叉树转换成树的方法相同，都是通过加线、去线和层次调整等操作来恢复树的结构。
2. 具体操作：见上文

画图如下：

然后，我们将分离的二叉树转换成树：

总结

树、森林和二叉树之间的转换是数据结构中的重要内容，它们相互关联，通过这种转换关系，我们可以更好地利用不同结构的特点和优势，在各种应用场景中高效地处理数据和解决问题。