[二叉树] 树 二叉树 森林相互转化

树转化成二叉树

1. 兄弟之间连线
2. 只留下与长子的连线
3. 顺时针旋转

TIM截图20181125184027.png

森林转换成二叉树

1. 每棵树转化为二叉树
2. 后一棵二叉树作为前一棵的右孩子,依次连接

二叉树转化成树

1. 若某个节点有左节点,把这个节点把左节点的所有右孩子(即右孩子的右孩子的右孩子...无限重复, 也可以理解为一直向右的路径)连接
2. 去掉所有节点与右孩子的连线
3. 旋转调整层次

二叉树转化成森林

1. 从根节点开始,去掉与右节点的连线,分离出右孩子为根的子树(注意: 对每棵子树的处理只看根节点有没有右孩子)
2. 对这棵新的子树重复1的操作,直到新的子树没有右孩子
3. 把所有的子二叉树转化为树