森林与二叉树的转换

树、森林与二叉树之间可以相互转换，转换的核心是孩子兄弟表示法（又称二叉链表表示法）。

核心原则

• 左指针 → 第一个孩子（长子）
• 右指针 → 下一个兄弟（右邻兄弟）

转换步骤

1. 在所有相邻兄弟之间加一条连线；
2. 对每个结点，只保留与第一个孩子的连线，删除与其他孩子的连线；
3. 以树根为轴，顺时针旋转 45° 整理。

手算示例

原始树：

       A
     / | \
    B  C  D
   / \
  E   F

步骤 1：加兄弟连线

       A
     / | \
    B--C--D
   / \
  E---F

步骤 2：只保留与第一个孩子的连线

       A
      /
     B---C---D
    /
   E---F

步骤 3：旋转整理，得到二叉树

     A
    /
   B
  / \
 E   C
  \   \
   F   D

转换步骤（树 → 二叉树的逆过程）

1. 从根开始，沿左孩子链找到所有结点；
2. 把每个结点的右孩子链上的结点，统统提升为它的兄弟（即挂到它双亲名下）；
3. 删除多余连线，整理层次。

手算示例

原始二叉树：

     A
    /
   B
  / \
 E   C
  \   \
   F   D

还原过程：

1. A 沿左链：A → B → E；
2. B 的右孩子 C → C 成为 B 的兄弟（即 A 的孩子）；
3. C 的右孩子 D → D 成为 C 的兄弟（即 A 的孩子）；
4. E 的右孩子 F → F 成为 E 的兄弟（即 B 的孩子）。

结果：

       A
     / | \
    B  C  D
   / \
  E   F

转换步骤

1. 将森林中每棵树分别转换为二叉树；
2. 第一棵树的根作为结果二叉树的根；
3. 第二棵树的根作为第一棵树根的右孩子；
4. 第三棵树的根作为第二棵树根的右孩子；依次类推。

手算示例（3 棵树的森林）

树1:      A          树2:    E        树3:    G
        /   \               /                / \
       B     C             F                H   I
      /
     D

步骤 1：各树分别转二叉树（左孩子右兄弟）

树1：            树2：      树3：
  A                E          G
 /                /          /
B                F          H
/ \                          \
D   C                         I

步骤 2：合并 —— 后一棵树的根接为前一棵树根的右孩子

        A
       / \
      B   E
     / \   \
    D   C   G
           /
          H
           \
            I

完整的最终二叉树（含 F）：

        A
       / \
      B   E
     / \  / \
    D   C F  G
            /
           H
            \
             I

1. 从根开始，沿右孩子链逐个断开，每个断点结点各作为一棵树的根；
2. 对得到的每棵二叉树，按「二叉树 → 树」的方法还原。