树的存储结构

树的存储结构主要有三种：双亲表示法、孩子表示法、孩子兄弟表示法。

一、双亲表示法

用一组连续空间存储结点，每个结点含 data 与 parent（父结点下标，根为 -1）：

#define MaxSize 100
typedef struct { ElemType data; int parent; } PTNode;   // parent：父结点下标，根为 -1
typedef struct { PTNode nodes[MaxSize]; int n; } PTree;

示例树 A(B(D,E),C(F)) 的双亲表示：

下标	data	parent
0	A	-1
1	B	0
2	C	0
3	D	1
4	E	1
5	F	2

优点：找父结点 O(1)；缺点：找孩子需遍历整个数组 O(n)。

二、孩子表示法

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 = 根位置

下标  data  孩子链表
 0    A  → [1] → [2] → NULL
 1    B  → [3] → [4] → NULL
 2    C  → [5] → NULL
 3    D  → NULL　…

优点：找孩子方便；缺点：找父结点需遍历。

三、孩子兄弟表示法（二叉链表）

typedef struct CSNode {
    ElemType data;
    struct CSNode *firstChild, *nextSibling;  // 第一个孩子、下一个兄弟
} CSNode, *CSTree;

示例：A(B,C,D) 且 B 有孩子 E、F：

     A
    /
   B        ← B 的左孩子 = 第一个孩子；右孩子 = 下一个兄弟 C
  / \
 D   E      ← 等价二叉树：D→E 相当于"E 是 D 的下一个兄弟"…

表示法	找父结点	找孩子	空间
双亲表示法	O(1)	O(n)	O(n)
孩子表示法	O(n)	O(1)	O(n+e)
孩子兄弟表示法	O(n)	O(第一个孩子)	O(n)