4.3.1 树向二叉树的转换

核心规则：左孩子右兄弟
转换方法：

1. 连兄弟线：在树中将所有兄弟节点用水平线连接。
2. 保留最左孩子：每个节点仅保留与最左孩子（长子）的连线，其余子节点连线删除。
3. 旋转调整：以根为轴心顺时针旋转45°，形成二叉树结构。

示例（图4.8示意）：

• 原树结构：

  A  
  ├─B  
  │ ├─E  
  │ └─F  
  ├─C  
  └─D  
  

• 转换后二叉树：

  A  
  └─B  
  ├─E  
  │ └─F  
  └─C  
    └─D  
  

• 说明：
• 节点B的左子树为长子E，右子树为兄弟C；
• 节点C的右子树为兄弟D；
• 节点E的右子树为兄弟F。

4.3.2 森林向二叉树的转换

核心规则：森林中每棵树转为二叉树后，按顺序链接为右子树链。
转换步骤：

1. 单棵树转换：将森林中的每棵树分别转换为二叉树（方法同4.3.1）。
2. 右子树链接：从最后一棵树开始，将其作为前一棵树的右子树。

示例（图4.9示意）：

• 原森林：

  森林 = [Tree1, Tree2, Tree3]  
  Tree1: A  
      / | \  
     B  C  D  
  Tree2: E  
        \  
         F  
  Tree3: G  
  

• 转换过程：
• 每棵树转为二叉树：
  • Tree1的二叉树：A(B, C(, D))
  • Tree2的二叉树：E(, F)
  • Tree3的二叉树：G
• 链接为右子树链：

   A  
   ├─B  
   └─C  
     ├─D  
     └─E  
       └─F  
         └─G  
  

• 说明：
• Tree1的根节点A的右子树为Tree2的根E；
• Tree2的根E的右子树为Tree3的根G。

示意图说明（文字描述）

1. 树转二叉树：

2. 兄弟节点转为右子树，长子转为左子树。

3. 原树的层次关系通过左子树深度和右子树宽度体现。

4. 森林转二叉树：

5. 森林中多棵树按顺序形成右子树链，每棵树内部遵循左孩子右兄弟规则。

公式补充：
对于树中节点$N$，其转换后的二叉树节点$N'$满足：

• $N'.left = \text{N的第一个孩子}$
• $N'.right = \text{N的下一个兄弟}$

通过这种方式，树和森林的结构得以在二叉树中高效存储和操作。