树，森林，二叉树之间的转换以及树，森林的遍历

1.树中的所有的兄弟节点之间加上一条线
2.对每个节点，除了保留与其长子的连线外，去掉该节点与其他孩子的连线。

将下图普通的树，转换为二叉树

1.树中的所有的兄弟节点之间加上一条线
树，森林，二叉树之间的转换以及树，森林的遍历
2.对每个节点，除了保留与其长子的连线外，去掉该节点与其他孩子的连线。

经过简单转变：

1.现将森林中的每颗树转换为二叉树
2.再将各个二叉树的根节点视为兄弟从左到右连在一起，这样，形成了一颗二叉树

现将下图中的森林转换为二叉树

树，森林，二叉树之间的转换以及树，森林的遍历

1.将森林中的每颗树转换为二叉树

树，森林，二叉树之间的转换以及树，森林的遍历

2…将各个二叉树的根节点视为兄弟从左到右连在一起

树，森林，二叉树之间的转换以及树，森林的遍历

形成二叉树
树，森林，二叉树之间的转换以及树，森林的遍历

和之前是逆序的

1.若节点x是其双亲y的左孩子，则把x的右孩子，右孩子的右孩子， . . . . . . 都与y连接起来。
2.去除所有双亲到右孩子之间的连线

如下图中的二叉树，
1.现有b符合第一点，将B的右孩子，右孩子的右孩子 . . . . . . 与A连接
树，森林，二叉树之间的转换以及树，森林的遍历

2.去除所有双亲到右孩子之间的连线
树，森林，二叉树之间的转换以及树，森林的遍历

普通树的遍历
分为先根遍历和后根遍历
以下图为例：
先跟遍历：A B E C F D G H I

后跟遍历：E B F C G H I D A 树，森林，二叉树之间的转换以及树，森林的遍历
森林的遍历也分为前序遍历和后序遍历，和树是一样的，只不过森林是树的集合。

我们进一步会发现：

树，森林的前跟遍历和二叉树的前序遍历结果相同
树，森林的后根遍历和二叉树的中序遍历结果相同

树，森林，二叉树之间的转换以及 树，森林的遍历