数据结构期末复习（ご）--二叉树，树，森林之间的转换
由森林(F)转换为二叉树(B)的规则：
设森林F有子树T1,T2,T3……；其中第一棵树比较特殊，单独拿出，T1分为root,t1,t2,t3,……
设二叉树B为LBT，ROOT，RBT.
- ROOT(T1)作为B(ROOT）
- T1的子树(t1,t2,t3,……,tm)作为LBT
- 其余的T2,T3,……，Tm作为RBT。
由二叉树转换为森林的规则：
- B(ROOT)作为T1(ROOT)
- LBT作为T1的子树(t1,t2,t3,……,tm)
- RBT作为其余的T2,T3,……，Tm
1.由树转换为二叉树：
- 树中所有相邻兄弟之间加一条连线
- 树中的每个节点，只保留其与第一个孩子节点之间的连线，删去其与其他孩子节点之间的连线
- 以树根节点为轴心，将整棵树顺时针旋转一定角度，使其更直观
注意：和树对应的二叉树，其左，右子树的概念已经变为：左是孩子，右是兄弟。
实例：
2.由森林转化为二叉树：
- 将森林中的每棵树转换成相应的二叉树
- 第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根节点作为前一棵二叉树根节点的右孩子，
- 当所有二叉树连在一起后，所得到的二叉树就是由森林转换得到的二叉树。
3.将二叉树转换为树或森林：
- 若某节点是其双亲的左孩子，则把该节点的右孩子，右孩子的右孩子……都与该节点的双亲节点用线连起来
- 删除原二叉树中所有双亲节点与右孩子节点的连线
- 整理即可得到相应的树或森林
版权声明：本文为DSYR原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。