树、森林 二叉树互转

树和森林可以与二叉树互相转换

(ps:因为找不到画图工具了，没有直接的连线方式，二叉树各个节点的连线本是没有方向的，而这里有方向，因为工具原因不严谨，见谅)

树的几种表示方式

先来看一下树的三种表示方法

1. 双亲表示法

   创建一个二维表格，描述当前节点的data和当前节点的双亲节点
   优点：显而易见，对于寻找该节点的双亲节点是非常容易的
   缺点：缺点也是显而易见的，查找双亲节点是非常方便，但是寻找孩子节点有可能会把整个树遍历一遍

   

数据	双亲
1	-1
2	0
3	0

2. 孩子表示法

创建一个二维表格，描述当前节点的data和当前节点的孩子节点
优点：与上一种表示方法相反，对于寻找孩子节点是非常容易的
缺点：寻找孩子节点非常容易，但是寻找双亲节点有可能会遍历整个树

数据	孩子
1	->2->3
2	^
3	^

3. 双亲孩子表示法

该方法是以上两种方法的结合，所具备前面两个表示方法的所有优点

1. 兄弟孩子表示法

   描述该节点的第一个孩子节点和该节点的兄弟节点。

   

   这样用孩子兄弟节点描述的话形如：

   

树、树林 转 二叉树

树、森林 -> 二叉树

先有一颗这样的树

让它转换为二叉树只需要用兄弟孩子表示法就行了

调整一下

森林 -> 二叉树

森林是由很多棵树组成的。

将森林转换为二叉树总共分两步

1. 将森林的所有树全部转为二叉树
2. 然后第一棵树不动，从第二棵树开始，一次把后一棵二叉树的根节点作为前一棵二叉树的右孩子进行连接

二叉树 -> 树和森林

二叉树转为树和森林其实就是树和森林转为二叉树的逆过程

总共分为以下两步过程

1. 若一个节点有左孩子，则把该节点的左孩子的右孩子，右孩子的右孩子…与该节点相连
2. 去掉原先的连线

比如现在有这样一棵二叉树

现在来进行第一步，如果某节点有左孩子，则把该节点的左孩子的右孩子，右孩子的右孩子…与该节点相连，

结果如下

去掉原先的连线，调整后如下

转换为了三棵树组成的森林