数据结构_树、二叉树、森林的转换

[toc]

树 转 二叉树

1. 加线。在所有兄弟结点之间加一条连线
2. 抹线。对树中的每个结点，只保留与第一个孩子之间连线，删除与其他孩子的连线
3. 整理。适当旋转一下，使之结构分明

森林 转 二叉树

1. 把每棵树转换成二叉树
2. 从第一棵二叉树开始，把后一棵二叉树作为前一棵二叉树根结点的右子树

二叉树 转 树

就是树 转 二叉树 的逆过程

1. 作为根结点的每个结点，与左孩子的右孩子以及这个右孩子的右孩子、右孩子的右孩子……建立连线
2. 删除原来所有父结点与右孩子的连线
3. 整理

图：见 树 转 二叉树 的dcba顺序

二叉树 转 森林

1. 删除原来所有父结点与右孩子结点的连线，得到分离的二叉树
2. 将分离的每棵二叉树转化为树