数据结构之树-树、二叉树、森林的相互转换-学习笔记-58

引入

我们学习了树、二叉树、以及森林的知识。我们直到遍历二叉树非常的方便,甚至学会了给二叉树增加线索,提高效率。那么问题来了,如果一棵树,不是二叉树,一个结点下有 N 个孩子,那么我们遍历和操作起来,就会很复杂,因为不知道这棵树是深度长还是宽度广,如果都能转换成二叉树来操作就爽了!今天我们就看看普通树和森林,如何转换成二叉树。

普通树转换为二叉树

既然二叉树最方便操作,我们如何能够将普通树转换成二叉树呢?

上面是一棵普通树,有三层,我们将这棵树转换成二叉树

第一步,操作兄弟结点

  • 兄弟结点就是位于二叉树同一层的所有结点
  • 同一个双亲的所有兄弟结点连接起来
  • 如果没有兄弟则不需要链接

第二步,去掉原有的连接线,规则如下

  • 每一个结点,只保留结点和其长子的连接线
  • 如果没有左孩子只有右孩子的话,那就保留右孩子的,以此类推
  • 去掉结点与其他孩子的连接线

第三步,变成二叉树

  • 仔细看就是前一张图的结点连接线
  • 红线表示左子树
  • 绿线表示右子树
  • 把二叉树画出来即可

森林转换为二叉树

森林转换为二叉树,其实跟刚才的普通树转换为二叉树差不多

  • 先将森林的每棵普通树转换为二叉树,不会的看上面。
  • 然后将森林里,每棵二叉树的根看做兄弟,进行连线
  • 每棵树的根,都是右子树,所以如果森林有三棵树
  • 那就是第一棵树作为二叉树的根,第二棵树是根的右子树,第三颗树是第二棵树的右子树

我们来看一个例子

这片森林有三棵树,每棵树都不是二叉树,我们将其先都转换成二叉树的形式

然后我们把三棵树的根连在一起,每棵树的根,都是右子树

然后我们根据普通树转二叉树的规则,再加上每棵树的根都是右子树,将森林转换成二叉树

二叉树转换到树、森林

第一步:我们知道如何将二叉树转换成树和森林,我们接着看看,如何反向转换

  • 如果一个结点 A,是结点 X 的左孩子
  • 那么这个结点 A 的右孩子的右孩子的右孩子…所有的右孩子
  • 都划线连接到 X,就是结点 A 的双亲
  • 我们看看下面的图

这张图就是根据上面的规则进行连线,我们来看一下

  • 先找哪些节点是双亲的左孩子,B、F、H
  • 再看看 B、F、H 有没有右子树,B 和 H 有
  • 接着看看 B 和 H 的右子树还有没有右子树,B的右子树下还有个 D
  • B 的右子树 C、B 的右子树的右子树 D 连接到 B 的双亲 A
  • H 的右子树 I 连接到 H 的双亲 G
  • Done!

第二步:去掉所有双亲到右孩子之间的连线

注意,G 到 I 是可以的,因为 H 才是 I 的双亲。

最后我们把二叉树转换回了森林。

注意:判断二叉树是森林还是普通树的方法是看二叉树的根节点有没有右子树,如果有,那根据倒推原理,一定是森林,没有就是普通树。

总结

普通树转换为二叉树

  • 加线:兄弟结点加线
  • 去线:每个结点都只保留与第一个孩子的连线
  • 调整:树本身的连线是左子树,我们划的线是右子树

森林转换为二叉树

  • 二叉:先把普通树都转换为二叉树
  • 连根:把所有二叉树的根连接起来
  • 调整:第一棵二叉树是根,其它根都是右孩子

二叉树转换为树、森林

  • 判断:判断根有没有右子树,有就是森林,没有就是普通树
  • 连线:把右孩子们和双亲链接在一起。
  • 去线:把所有结点到右孩子的连线去掉
  • 调整:剩下的就是普通树或者森林

思考

我们为什么费劲把普通树和森林转换为二叉树呢?
因为普通树和森林遍历不方便。

普通树的遍历

如果我们使用先根的方法遍历普通树

  • 先输出根
  • 然后从左到右输出全部子树
  • 然后再从左到右输出子树的子树
  • 依次类推

同样的,如果我们使用后根的方法遍历普通树

  • 先输出子树
  • 然后再从左到右输出子树的双亲
  • 依次类推

我们看看例题

先根遍历结果是:A B E F C G D H I J
后根遍历结果是:A B E F C G D H I J

森林的遍历

其实森林的遍历跟树的遍历一样

  • 第一棵结束就下一棵
  • 然后把所有的便利结果放在一起就行了

发现

前人们惊人的发现了以下事实,对于森林、树的遍历和二叉树的遍历

  • 森林、树的前根遍历 等同于 二叉树的前序遍历
  • 森林、树的后跟遍历 等同于 二叉树的中序遍历

好了!有意思的事情来了!下节继续!

尾巴

这是我的个人学习笔记,主要是应付考研复习使用,充斥着一些吐槽和个人观点,并不严谨,欢迎大家参考、指正。


-------------The End-------------
欢迎请我喝咖啡哦~!