树与二叉树的相互转换
树->二叉树
- 加线
把相应结点的兄弟结点连线
-
去线
去掉双亲和非最左边孩子的连线 -
旋转
二叉树->树
- 加线-去线
将结点与其左孩子的右孩子及其右子孙连线。然后去掉所有结点与其右孩子的连线。
- 旋转处理
得到二叉树
#森林->二叉树
- 先将每棵树转换为二叉树
- 连接每棵树的根结点
- 以第一颗树的根作为二叉树的根顺时针旋转
#二叉树->森林
- 将二叉树的根结点与其右孩子及右子孙的连线全部去掉
- 对剩下的每一棵孤立的二叉树按照二叉树与树的转换规则转换为树
- 得到森林
树的遍历过程
- 先根序遍历
- 后根序遍历
- 层次遍历
为什么树没有中序遍历？
因为对于树来说其孩子结点可能有多个，无法确定中序的“中”。
森林的遍历过程
- 先序遍历
- 中序遍历
为什么森林没有后序遍历？
因为对于森林来说，后序遍历每颗树，称为其中序遍历。而没有符合定义的后序遍历的规则，如果定义树的后序遍历为后根，也无法具体确定实现每一棵树的次序。