树、森林与二叉树的转换及遍历

Dear 丶 2022-06-14 12:24 240阅读 0赞

# 1.树、森林与二叉树的转换 #

前面介绍的孩子兄弟存储结构可以将树转换为二叉树。这样我们就可以使用二叉树的算法来解决普通树的问题。

## 1.树转换为二叉树 ##

将树转换为二叉树的步骤如下：

1.  **加线**。在所有相邻的兄弟结点之间加一条线。
2.  **去线**。对树中的每个结点。只保留它与第一个孩子结点的连线，删除它与其他孩子结点之间的连线。
3.  **层次调整**。原来结点第一个孩子是二叉树结点的左孩子，兄弟转换过来的孩子是结点的右孩子。

![图1][1]

## 2.森林转换为二叉树 ##

将森林转换为二叉树的步骤如下：

1.  把每棵树都转换为二叉树。
2.  第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树根结点的右孩子，用线连接起来。当所有二叉树连接起来后就得到了由森林转换来的二叉树。  
    ![图2][2]

## 3.二叉树转换为树 ##

二叉树转换为树是树转换为二叉树的逆过程：

1.  **加线**。若某结点左孩子存在，则将该左孩子的结点的右孩子结点、右孩子的右孩子结点、右孩子的右孩子的右孩子结点。。。。即左孩子下属的所有右孩子结点都作为该结点的孩子。将该结点与这些右孩子结点用线连接起来。
2.  **去线**。将原二叉树中所有结点与其右孩子结点的连线删除。
3.  **层次调整**。
4.  二叉树转换为森林

--------------------

判断一棵树能够转换为一棵树还是森林，只需看这颗二叉树根结点是否具有右孩子，有右孩子就是森林，没有右孩子就是一棵树。转换为森林的步骤如下：

1.  从根结点开始，若右孩子存在，则把右孩子结点的连线删除，再查看分离后的右子树，若该右子树的根结点右孩子存在，则连线删除，直到所有右孩子连线都删除为止，得到若干分离的二叉树。
2.  将每棵二叉树转换为树。

# 2.树和森林的遍历 #

## 1.树的遍历 ##

由树结构定义可引出两种次序遍历树的方法：一种是**先根遍历**，即先访问树的根结点，然后依次先根遍历根的每棵子树。另一种是**后根遍历**，即先依次后根遍历每棵子树，然后再访问根结点。例如对下图中的树进行遍历，其先根遍历为：ABEFCDG；后根遍历为：EFBCGDA。  
\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ka3cGMQ7-1586162371190)(https://img-blog.csdn.net/20170620165758138?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvemp3X3B5dGhvbg==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast)\]

## 2.森林的遍历 ##

森林的遍历也分为两种方式：一种是**先序遍历**，即先访问森林中第一棵树的根结点，再先根遍历第一棵树的子树，再依次用同样方式遍历除去第一棵树的剩余树构成的森林。另一种是**后序遍历**，即先后根遍历森林中第一棵树的子树，再访问第一棵树的根结点，然后依次用同样方式遍历除去第一棵树的剩余树构成的森林。例如对下图的森林进行遍历，其先序遍历为：ABCDEFGHJI；后序遍历为：BCDAFEJHIG。  
![图4][4]  
我们可以看见，森林的先序遍历和后序遍历与其对应的二叉树的先序遍历和中序遍历相同。由此可见，当以二叉链表作树的存储结构时，树的先根遍历和后根遍历可借用二叉树的先序遍历和中序遍历算法实现。

--------------------

如果觉得这篇文章帮助了您，请打赏一个小红包鼓励作者继续创作哦！！！

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3pqd19weXRob24_size_16_color_FFFFFF_t_70_pic_center]

[1]: /images/20220614/755531e392be4dd79cc854ab558d65c2.png
[2]: /images/20220614/5f72987bca5e43d0917227f1e24cc166.png
[4]: /images/20220614/38ce9a0ce923436fa9e63af347ce353b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3pqd19weXRob24_size_16_color_FFFFFF_t_70_pic_center]: /images/20220614/cb067a361b5a412cbb6c9ecac98e672f.png