树与森林

• 存储结构：

  • 双亲表示法：数组存储，找父节点 $O(1)$，找孩子难。
  • 孩子表示法：数组+链表，类似图的邻接表。
  • 孩子兄弟表示法 (二叉链表)：最重要。
    • 左指针 → 第一个孩子 (First Child)
    • 右指针 → 下一个兄弟 (Next Sibling)
    • 口诀：左孩右兄。

• 转换 (Conversion)：

  • 树转二叉树：加线（兄弟间）、抹线（只留第一个孩子）、旋转。
  • 森林转二叉树：将每棵树转为二叉树，然后根节点依次相连（作为右孩子）。