408

数据结构

DS-04-02 二叉树的顺序存储与链式存储

---

一、定位信息

项目	内容
圈层	核心层（大纲考点）
前置知识	二叉树的定义与性质、数组存储、指针与链表
知识网络定位	本单元是二叉树操作的物理实现基础，是遍历、线索化等算法的前提
考点热度	M级（中频常考）：近5年出现约2-3次，常以选择题或代码填空形式考查

---

二、知识点讲解

2.1 顺序存储

定义：用一组连续的存储单元（数组）存储二叉树的节点，节点的存储位置隐含了节点之间的逻辑关系。

存储规则：

• 将二叉树按完全二叉树的方式进行层序编号
• 编号为 $i$ 的节点存储在数组下标为 $i$ 的位置（下标从1开始，0号位置空置或存节点数）
• 若使用下标从0开始，则编号为 $i$ 的节点存于 $a[i-1]$

适用场景：完全二叉树和满二叉树最适合顺序存储，因为不存在空间浪费。

空间浪费问题：对于一般的二叉树，特别是右斜树（每个节点只有右孩子），顺序存储会造成极大的空间浪费。一棵深度为 $k$ 的右斜树只有 $k$ 个节点，但需要 $2^k - 1$ 个存储单元。

存储示例：

【图示说明】完全二叉树：
        1(A)
       / \
      2(B) 3(C)
     / \   /
    4(D) 5(E) 6(F)

顺序存储：[空, A, B, C, D, E, F]
下标：      0   1   2   3   4   5   6

父子关系（下标从1开始）：

• 节点 $i$ 的左孩子：$2i$（若 $2i \leq n$）
• 节点 $i$ 的右孩子：$2i+1$（若 $2i+1 \leq n$）
• 节点 $i$ 的父节点：$\lfloor i/2 \rfloor$（若 $i > 1$）

2.2 链式存储（二叉链表）

定义：每个节点包含一个数据域和两个指针域，分别指向左孩子和右孩子。

节点结构：

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

指针利用情况：$n$ 个节点的二叉链表共有 $2n$ 个指针域，其中 $n-1$ 个指向孩子节点（除根节点外每个节点有一个入边），剩余 $n+1$ 个指针域为空。这 $n+1$ 个空指针在后续线索二叉树中将被利用。

空间分析：每个节点占 $\text{sizeof(ElemType)} + 2 \times \text{sizeof(指针)}$ 字节。对于 $n$ 个节点，总空间为 $n \times (\text{sizeof(ElemType)} + 2 \times \text{sizeof(指针)})$。相比顺序存储，链式存储不会因树的形态不同而浪费空间，但每个节点有额外的指针开销。

2.3 三叉链表（扩展）

在二叉链表基础上增加一个指向双亲的指针域：

typedef struct TriTNode {
    ElemType data;
    struct TriTNode *lchild;
    struct TriTNode *rchild;
    struct TriTNode *parent;    // 双亲指针
} TriTNode, *TriTree;

优势：可以方便地从任意节点向上追溯到根节点，时间复杂度为 $O(h)$（$h$ 为树高）。适用于需要频繁查找祖先节点的场景。

2.4 两种存储方式对比

对比项	顺序存储	链式存储（二叉链表）
存储方式	数组，按层序编号	节点+指针
空间利用	完全二叉树高效，一般二叉树浪费	无浪费，但每节点有指针开销
找父节点	$O(1)$，直接计算	$O(h)$，需遍历（除非用三叉链表）
找子节点	$O(1)$，直接计算	$O(1)$，直接跟随指针
插入/删除	需移动大量元素，$O(n)$	修改指针，$O(1)$（找到位置后）
适用场景	完全二叉树、满二叉树、堆	一般二叉树
空间复杂度	$O(2^k)$（$k$ 为深度）	$O(n)$

---

三、记忆与理解辅助

技巧1：顺序存储编号口诀

"左二右二加一，父除二取整"

• 左孩子：编号 $\times 2$
• 右孩子：编号 $\times 2 + 1$
• 父节点：编号 $\div 2$ 取整

技巧2：二叉链表空指针数

"$n$ 节点二叉链，$n+1$ 空指针" 总指针 $2n$，有效指针 $n-1$（除根外每个节点一条入边），空指针 $2n - (n-1) = n+1$

技巧3：存储方式选择速查

问题场景	推荐存储
完全二叉树/堆	顺序存储
需频繁遍历	链式存储
需找祖先	三叉链表
哈夫曼树	链式存储（形态不规则）

---

四、例题与精解

例题1（基础巩固）

题目：一棵二叉树的顺序存储数组为 [空, A, B, C, D, E, 空, G, 空, 空, H]（下标从0开始，0号位置空置），请画出该二叉树的逻辑结构。

命题意图：考查顺序存储到逻辑结构的转换能力。

审题分析：下标1到10依次存储节点，空表示该位置无节点。需按层序编号还原。

解题思路：利用父子关系 $\text{left}(i) = 2i$，$\text{right}(i) = 2i+1$，逐层还原。

完整步骤：

Step 1：列出有效存储：

下标	1	2	3	4	5	6	7	8	9	10
节点	A	B	C	D	E	空	G	空	空	H

Step 2：确定父子关系：

• 节点1(A)：左孩子=2(B)，右孩子=3(C)
• 节点2(B)：左孩子=4(D)，右孩子=5(E)
• 节点3(C)：左孩子=6(空)，右孩子=7(G)
• 节点5(E)：左孩子=10(H)，右孩子=11(超出范围)

Step 3：画出二叉树：

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

答案：如上图所示。

方法反思：顺序存储还原时，注意"空"位置表示无节点，但该编号仍被占用，后续编号不受影响。

例题2（中等提升）

题目：一棵有 $n$ 个节点的二叉树采用二叉链表存储，编写一个算法计算该树中叶子节点的个数。

命题意图：考查二叉链表的递归操作，为遍历算法做铺垫。

审题分析：叶子节点的特征是左右孩子均为空，需要遍历所有节点判断。

解题思路：用递归方式，若当前节点为空返回0，若为叶子返回1，否则返回左右子树叶子数之和。

完整步骤：

// 函数功能：计算二叉树的叶子节点数
// 参数 T：二叉树的根节点指针
// 返回值：叶子节点个数
int CountLeaf(BiTree T) {
    // 基本情况：空树没有叶子
    if (T == NULL) {
        return 0;
    }
    // 叶子节点：左右孩子都为空
    if (T->lchild == NULL && T->rchild == NULL) {
        return 1;
    }
    // 递归：左子树叶子数 + 右子树叶子数
    return CountLeaf(T->lchild) + CountLeaf(T->rchild);
}

方法反思：

1. 递归三要素：终止条件、递归体、返回值
2. 空树返回0，叶子返回1，非叶子返回子树之和
3. 时间复杂度 $O(n)$，空间复杂度 $O(h)$（递归栈深度等于树高）

---

五、考情分析

项目	内容
考查频次	近5年约2-3次，多为选择题
常见题型	选择题（顺序存储的空间分析、指针域数量）、代码填空（链式存储操作）
分值占比	选择题2分左右
命题趋势	常与遍历算法结合考查，单独出题较少但作为基础不可或缺
典型考点	$n$ 个节点的二叉链表有 $n+1$ 个空指针；顺序存储中父子编号关系

---

六、易错点提醒

易错点1

• 错误表现：顺序存储时下标从0开始还是从1开始搞混
• 错误原因：不同教材的约定不同，严蔚敏版从1开始，部分教材从0开始
• 正确理解：从1开始时，父子关系为 $2i$、$2i+1$、$\lfloor i/2 \rfloor$；从0开始时，父子关系为 $2i+1$、$2i+2$、$\lfloor (i-1)/2 \rfloor$。考试时务必看清题目约定

易错点2

• 错误表现：计算二叉链表空指针时，误算为 $n-1$ 或 $2n$
• 错误原因：混淆了"有效指针数"和"空指针数"
• 正确理解：总指针 $2n$，有效指针 $n-1$（树的边数），空指针 $2n-(n-1) = n+1$

易错点3

• 错误表现：认为顺序存储适用于所有二叉树
• 错误原因：忽略了右斜树等极端情况下空间浪费严重的问题
• 正确理解：顺序存储仅对完全二叉树和满二叉树空间高效。对于一般二叉树，特别是深度较大但节点较少的情况，应使用链式存储

易错点4

• 错误表现：将"二叉链表"和"三叉链表"的适用场景混淆
• 错误原因：未理解指针域的作用
• 正确理解：二叉链表只能从上往下找孩子；三叉链表增加了parent指针，可以向上追溯祖先

---

七、来源标注

• 依据2026考研统考408大纲
• 依据《数据结构（C语言版）》严蔚敏版
• 依据《数据结构》王道考研辅导讲义