二叉树的存储结构

定义

用一组连续的存储单元，按层序编号存储二叉树的结点。

#define MaxSize 100
typedef struct {
    ElemType data[MaxSize];  // 从下标 1 开始存储
    int n;                   // 结点数
} SqBiTree;

编号规则

• 根结点编号为 1
• 结点 $i$ 的左孩子：$2i$
• 结点 $i$ 的右孩子：$2i+1$
• 结点 $i$ 的双亲：$\lfloor i/2 \rfloor$

示例

           A
         /   \
        B     C
       / \     \
      D   E     F

存储为：[_, A, B, C, D, E, _, F]（下标 0 不用；6 号位空缺，因为 C 没有左孩子）

优缺点与适用场景

定义

typedef struct BiTNode {
    ElemType data;
    struct BiTNode *lchild, *rchild;  // 左右孩子指针
} BiTNode, *BiTree;

结点结构

┌──────────┬──────────┬──────────┐
│  lchild  │   data   │  rchild  │
│  左孩子   │  数据域   │  右孩子   │
└──────────┴──────────┴──────────┘

空指针数 = $n+1$

证明：

• 指针总数：$2n$（每个结点 2 个指针）
• 非空指针数：$n-1$（除根外每个结点恰被一个指针指向）
• 空指针数：$2n-(n-1) = n+1$

示例核对

仍用上面的树（$n=6$）：

A: lchild→B,   rchild→C
B: lchild→D,   rchild→E
C: lchild=NULL, rchild→F
D: lchild=NULL, rchild=NULL
E: lchild=NULL, rchild=NULL
F: lchild=NULL, rchild=NULL

空指针数 $= D(2)+E(2)+F(2)+C(1) = 7 = 6+1$ ✓

typedef struct TriTNode {
    ElemType data;
    struct TriTNode *lchild, *rchild, *parent;  // 增加父指针
} TriTNode, *TriTree;

┌──────────┬──────────┬──────────┬──────────┐
│  parent  │  lchild  │   data   │  rchild  │
│  双亲指针 │  左孩子   │  数据域   │  右孩子   │
└──────────┴──────────┴──────────┴──────────┘

• 优点：查找双亲由 $O(n)$ 降为 $O(1)$。
• 缺点：每结点多占一个指针，总共 $3n$ 个指针域。

例 1：顺序存储空间计算

完全二叉树有 100 个结点，用顺序存储需要多少空间？

• 深度 $k = \lfloor \log_2 100 \rfloor + 1 = 6+1 = 7$
• 同深度满二叉树结点数：$2^7-1 = 127$
• 但完全二叉树编号连续，只需存到 100 号
• 需要空间：$100+1 = 101$ 个存储单元（下标 0 不用）

例 2：空指针计算

二叉树有 50 个结点，二叉链表中有多少空指针？
空指针数 $= n+1 = \textbf{51}$。

例 3：由顺序存储还原二叉树

顺序存储：[_, A, B, C, D, E, _, F, G]

           A
         /   \
        B     C
       / \     \
      D   E     F
     /
    G