大话数据结构_树森林二叉树转换与遍历

树转二叉树

1. 加线
2. 去线
3. 层序调整（第一个孩子是二叉树的左节点，兄弟转化过来的孩子是二叉树的右节点）

森林转为二叉树

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

二叉树转树

1. 加线

   1. 如果一个节点A的左孩子节点存在，将这个节点A的右孩子节点、右孩子的右孩子节点、右孩子的右孩子的右孩子的节点...作为A的孩子节点，并用线连接起来

2. 去线

   1. 删除原二叉树中所有节点与其右孩子节点的连线

3. 层次调整

二叉树转森林

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

树与森林遍历

1. 前序遍历
   1. 先访问森林中第一棵树的根结点，然后再依次先根遍历根的每棵子树，再依次用同样方式遍历除去第一棵树的剩余树构成的森林。
2. 后序遍历
   1. 先访问森林中的第一棵树，后根遍历的方式遍历每棵子树，然后再访问根结点，再依次同样方式遍历除去第一棵树的剩余树构成的森林。