数据结构-树、森林、二叉树的相互转换

一棵树转换成一棵二叉树

一棵树转换成二叉树的过程：
①树中所有相邻兄弟之间加一条连线。

②对树中的每个结点只保留它与长子（即最左边的孩子结点）之间的连线，删除与其他孩子之间的连线。

③以树的根节点为轴心，将整棵树顺时针转动45°，使结构层次分明。

例题1：

Step 1：

Step 2：

Step 3：

---

例题2：

Step 1：

Step 2：

Step 3：

---

一棵二叉树转换成一棵树

一棵二叉树转换成一棵树的过程：
①若某结点是其双亲的左孩子，则把该结点的右孩子、右孩子的右孩子等都与该结点的双亲结点用连线连起来。

②删除原二叉树中所有双亲结点与右孩子结点之间的连线。

③以根节点为轴心，逆时针转动45°，使结构层次分明。

例题1：

Step 1：

Step 2：

Step 3：

Step 4：

Step 5：

例题2：

---

森林转换一棵二叉树

森林转换一棵二叉树的过程：
①将森林中的每棵树转换成相应的二叉树。

②第一颗二叉树不动，从第二棵二叉树开始，依次把后一棵树的根节点作为前一棵二叉树的根节点的右孩子结点。

Step 1：

Step 2：

---

一棵二叉树转换森林

一棵二叉树转换森林的过程：
①抹掉二叉树根节点右链上的所有结点之间的“双亲-右孩子”关系，将其分成若干个以右链上的结点为根节点的二叉树，设这些二叉树bt₁、bt₂、…bt_m。

②分别将二叉树bt₁、bt₂、…bt_m各自还原成一棵树。

Step 1：

Step 2：