树,森林,二叉树的相互转换

1. 普通树到二叉树的转换

1.1. 步骤:

1. 在树的所有兄弟节点间连线
2. 保留所有结点与第一个左孩子的连线和兄弟线, 其他线统统去掉
3. 保持结点的左右孩子顺序不变, 转换视角为二叉树
   1. 左孩子作左子树, 右兄弟作右子树

1.2. 性质:

1. 转换得到的二叉树唯一
2. 转换得到的二叉树只有左子树, 没有右子树

2. 森林到二叉树的转换

2.1. 步骤:

1. 将每棵树变成二叉树
2. 在每棵树的根之间连线

2.2. 性质:

1. 转换得到的二叉树既有左子树, 又有右子树

3. 二叉树转换为普通树或森林

3.1. 梗概:

1. 如果二叉树没有右子树, 转换后得到普通树
2. 如果二叉树有右子树, 转换后得到森林

3.2. 步骤:

1. 对所有的结点, 连接到其左子树的右孩子, 连接到左子树的右子树的右孩子…
2. 去掉所有结点与右孩子的连线