5.2.2 二叉树的顺序与链式存储

顺序存储最适合完全二叉树，按层序编号可直接计算亲属下标。对稀疏斜树，最高编号可能指数增长，大量数组槽为空。链式存储用 left/right 指针，只为实际结点分配空间，适合一般形态。

手工推演

一棵 4 结点右斜树按 1 基编号依次占 1、3、7、15，数组至少开到 15；链式存储只需 4 个结点。含 $n$ 个结点的二叉链表共有 $2n$ 个孩子指针，实际边 $n-1$ 条，空指针数为 $2n-(n-1)=n+1$。

结构与代码

typedef struct BNode{int data;struct BNode *left,*right;}BNode;

创建结点时两个指针都应初始化为 NULL。释放时应后序处理：先释放左右子树，再释放根，避免丢失子树地址。

错解反馈

认为链式存储能 $O(1)$ 找双亲，普通二叉链表没有父指针；数组下标直接等于逻辑位序；统计空指针时把根也当一条入边，都会出错。

迁移练习

7 个结点的二叉链表有多少空指针？答案 8。独立验收：能用指针总数减实际边数推导，并比较完全树与斜树的空间。