二叉树的存储：顺序存储/链式存储

1. 顺序存储（数组）

  • 适用：完全二叉树或满二叉树。
  • 原理：按层序编号，将结点存入数组对应下标位置。
  • 优点：无需指针，内存紧凑，访问快速（通过下标计算父子关系）。
  • 缺点：一般二叉树会浪费大量空间（存储 NULL 标记）。

存储方式

1
2
3
# 用数组存储完全二叉树，索引从 1 开始
tree = [None] * (n + 1)   # tree[1] 为根
# 结点 i 的左孩子为 2*i，右孩子为 2*i+1

空间浪费举例

  • 深度为 h 的右斜树，需要 2h−12^h - 1 个数组空间，实际只用了 h 个。

2. 链式存储（二叉链表）

  • 适用：一般二叉树。

  • 结构：每个结点包含数据域、左指针（lchild）、右指针（rchild）。

  • 优点：无空间浪费，灵活。

  • 缺点：需要额外指针开销（约 2n2n 个指针域）。

1
2
3
4
typedef struct BiTNode {
    ElemType data;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

3. 三叉链表（增加双亲指针）

  • 结构：在二叉链表基础上增加一个指向双亲的指针 parent。

  • 优点：便于寻找父结点，如平衡树调整。

  • 缺点：空间开销更大。

1
2
3
4
5

typedef struct TriTNode {
    ElemType data;
    struct TriTNode *lchild, *rchild, *parent;
} TriTNode;

对比总结

存储方式 适用树类型 查找孩子 查找双亲 空间效率 常用场景
顺序存储 完全二叉树 O(1) O(1) 高（无浪费） 堆
二叉链表 任意二叉树 O(1) O(h) 中（有指针） 一般二叉树操作
三叉链表 需频繁找父结点 O(1) O(1) 低 AVL、红黑树等