树和森林

一、树的存储结构

1. 双亲表示法：用数组存储，每个结点记录双亲位置。找双亲 $O(1)$，找孩子需遍历 $O(n)$。

typedef struct { ElemType data; int parent; } PTNode;   // parent = 双亲下标
typedef struct { PTNode nodes[MaxSize]; int n; } PTree;

2. 孩子表示法：每个结点用链表存储所有孩子。找孩子方便，找双亲需遍历。

typedef struct CTNode { int child; struct CTNode *next; } CTNode;
typedef struct { ElemType data; CTNode *firstchild; } CTBox;   // 孩子链表头
typedef struct { CTBox nodes[MaxSize]; int n, r; } CTree;      // r = 根位置

3. 孩子兄弟表示法（二叉链表）：找第一个孩子 $O(1)$、找下一个兄弟 $O(1)$，可转换为二叉树。

typedef struct CSNode {
    ElemType data;
    struct CSNode *firstchild, *nextsibling;  // 第一个孩子、右兄弟
} CSNode, *CSTree;

         A
       / | \           孩子兄弟表示：
      B  C  D          A → firstchild → B → nextsibling → C → nextsibling → D
     / \                                    ↓
    E   F                                   E → nextsibling → F

二、树、森林与二叉树的转换

树 → 二叉树（左孩子右兄弟）：

1. 所有兄弟结点之间加连线
2. 对每个结点只保留与第一个孩子的连线
3. 以树根为轴心顺时针旋转 45°

二叉树 → 树（逆过程）：加线（左孩子的右链逐级连回父）、去线（删除所有右孩子连线）、层次调整。

森林 → 二叉树：先将每棵树转为二叉树，再把各树根视为兄弟用右指针连接。

三、树的遍历

• 先根遍历：先访问根，再遍历各子树 —— 等价于二叉树先序遍历
• 后根遍历：先遍历各子树，再访问根 —— 等价于二叉树中序遍历
• 层次遍历：从上到下、从左到右，用队列

森林遍历：先序遍历（访问第一棵根→子树→剩余森林）等价二叉树先序；中序遍历等价二叉树中序。