树的存储结构

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

1. 双亲表示法

  • 实现：用一组连续空间存储结点，每个结点附加一个指针（下标）指向其双亲。
  • 优点：容易找到双亲。
  • 缺点：找孩子需要遍历。
1
2
3
4
5
6
7
8
typedef struct {
    ElemType data;
    int parent;   // 双亲位置下标（-1 表示根）
} PTNode;
typedef struct {
    PTNode nodes[MAX_SIZE];
    int n;        // 结点数
} PTree;

2. 孩子表示法

  • 实现：用数组存储结点，每个结点维护一个链表，链接其所有孩子。

  • 优点：容易找到孩子。

  • 缺点：找双亲需要遍历。

1
2
3
4
5
6
7
8
9

typedef struct ChildNode {
    int child;                 // 孩子下标
    struct ChildNode *next;
} ChildNode;
typedef struct {
    ElemType data;
    ChildNode *firstChild;
} CTBox;

3. 孩子兄弟表示法（又称二叉链表表示法）

  • 实现：每个结点包含 数据域、第一个孩子指针 和 右兄弟指针。

  • 优点：可以将任意一棵树转化为二叉树存储，方便处理。

  • 转换规则：左指针指向第一个孩子，右指针指向下一个兄弟。

1
2
3
4
5
typedef struct CSNode {
    ElemType data;
    struct CSNode *firstChild;   // 左孩子
    struct CSNode *nextSibling;  // 右兄弟
} CSNode, *CSTree;

存储结构对比

存储方式 找双亲 找孩子 空间利用率 常用场景
双亲表示法 快 慢 中等 并查集
孩子表示法 慢 快 低 一般树操作
孩子兄弟表示法 需遍历 快 较高 树与二叉树的转换

总结

  • 双亲表示法适合自底向上的操作（如并查集）。

  • 孩子表示法适合自上而下的遍历。

  • 孩子兄弟表示法是树转化为二叉树的常用手段，便于复用二叉树算法。