【数据结构】二叉树的存储结构（顺序/链式）
考点频率：★★★★☆（选择题常考，是理解二叉树遍历和操作的基础）
难度：⭐⭐
建议：重点掌握顺序存储的适用范围（完全二叉树）和链式存储的节点结构
1️⃣ 存储结构概述
在上一篇文章中，我们学习了二叉树的五大性质。但光有性质还不够——数据最终要存到计算机里才能用。二叉树的存储方式主要有两种：
- 顺序存储：用数组存储，适合完全二叉树
- 链式存储：用链表存储，适合所有二叉树
打个比方：顺序存储就像固定座位的电影院——每个座位（数组下标）对应一个固定位置，适合人员固定（完全二叉树）的场景。链式存储就像自由入座的教室——每个人（节点）记住自己左边和右边是谁，灵活性高，适合任意形状的群体（任意二叉树）。
2️⃣ 顺序存储（Sequential Storage）
2.1 核心思想
将二叉树的节点按照从上到下、从左到右的顺序，依次存储到一维数组中。节点在数组中的下标位置，直接反映了它在树中的逻辑位置。
基于的性质：完全二叉树的编号规律（性质5）——对于编号为i ii的节点：
- 左子节点位置：2 i 2i2i
- 右子节点位置：2 i + 1 2i + 12i+1
- 父节点位置：⌊ i / 2 ⌋ \lfloor i/2 \rfloor⌊i/2⌋
2.2 存储规则
| 规则 | 说明 |
|---|---|
| 数组下标从1开始（或从 0 开始，考试常考从1开始） | 下标1存储根节点 |
| 节点i ii的左子节点存储在2 i 2i2i | 如果2 i ≤ n 2i \le n2i≤n |
| 节点i ii的右子节点存储在2 i + 1 2i+12i+1 | 如果2 i + 1 ≤ n 2i+1 \le n2i+1≤n |
空节点用特殊值（如#或0）占位 | 保持数组位置的对应关系 |
示例：完全二叉树
1 / \ 2 3 / \ \ 4 5 6顺序存储为：[1, 2, 3, 4, 5, 6]（下标从1开始）
2.3 顺序存储的适用场景
| 适用场景 | 原因 |
|---|---|
| 完全二叉树 | 节点位置紧凑，数组空间利用率高 |
| 满二叉树 | 所有位置都被填满，空间利用率100% |
2.4 顺序存储的痛点（考点）
对于一般二叉树（非完全二叉树），顺序存储会浪费大量空间。
1 / \ 2 3 / \ 4 5顺序存储：[1, 2, 3, 4, #, #, 5]（中间两个空位用#占位）
关键点：一般二叉树如果用顺序存储，必须把空缺的位置也用特殊值占位，导致数组中有大量空闲空间。最坏情况下，一棵深度为k kk的二叉树，即使只有k kk个节点，也需要2 k − 1 2^k - 12k−1长度的数组。这就是为什么一般二叉树不用顺序存储。
3️⃣ 链式存储（Linked Storage）
3.1 核心思想
用链表来存储二叉树，每个节点包含数据域和两个指针域（分别指向左子节点和右子节点）。节点之间通过指针连接，物理上可以分散存储。
3.2 节点结构
typedefstructBiTNode{intdata;// 数据域structBiTNode*lchild;// 左子节点指针structBiTNode*rchild;// 右子节点指针}BiTNode,*BiTree;3.3 三种遍历方式在链式存储中的实现
| 遍历方式 | 访问顺序 | 代码逻辑（伪代码） |
|---|---|---|
| 先序遍历（Preorder） | 根 → 左 → 右 | 访问根; 先序(左子树); 先序(右子树) |
| 中序遍历（Inorder） | 左 → 根 → 右 | 中序(左子树); 访问根; 中序(右子树) |
| 后序遍历（Postorder） | 左 → 右 → 根 | 后序(左子树); 后序(右子树); 访问根 |
示例：对上面的树进行遍历
1 / \ 2 3 / \ \ 4 5 6- 先序：
1 2 4 5 3 6 - 中序：
4 2 5 1 3 6 - 后序：
4 5 2 6 3 1
4️⃣ 顺序存储 vs 链式存储（对比表）
| 对比项 | 顺序存储 | 链式存储（二叉链表） |
|---|---|---|
| 底层结构 | 数组 | 链表（指针） |
| 适用范围 | 完全二叉树/满二叉树 | 所有二叉树 |
| 存储密度 | 完全二叉树：高；一般二叉树：低（大量空位） | 低（每个节点两个指针，约50%） |
| 查找父节点 | 直接计算⌊ i / 2 ⌋ \lfloor i/2 \rfloor⌊i/2⌋，O ( 1 ) O(1)O(1) | 需要遍历，O ( n ) O(n)O(n) |
| 查找子节点 | 直接计算2 i 2i2i或2 i + 1 2i+12i+1，O ( 1 ) O(1)O(1) | 通过指针访问，O ( 1 ) O(1)O(1) |
| 插入/删除 | 困难（需要移动大量元素） | 简单（修改指针） |
| 空间浪费 | 一般二叉树浪费严重 | 每个节点固定指针开销 |
5️⃣ 经典例题
例题1（顺序存储的适用性）：以下哪种二叉树最适合采用顺序存储？
A. 满二叉树
B. 只有右子树的二叉树
C. 深度为10的任意二叉树
D. 每个节点只有一个子节点的二叉树
解析：满二叉树和完全二叉树最适合顺序存储，因为数组中没有空位浪费。满二叉树的节点编号是连续的，可以100%利用数组空间。选A。
例题2（三叉链表的改进）：如果需要在二叉树中频繁查找某个节点的父节点，应该选择什么存储结构？
A. 顺序存储
B. 普通二叉链表（无父指针）
C. 三叉链表（增加父指针）
D. 循环链表
解析：三叉链表在普通二叉链表的基础上增加了父指针，查找父节点时不需要遍历，直接访问即可。软考中考到这个概念时，知道它的作用是快速查找父节点即可。选C。
例题3（判断）：顺序存储结构适用于所有类型的二叉树。（ ）
解析：错误。顺序存储只适用于完全二叉树（和满二叉树），对于一般二叉树会造成大量空间浪费。
6️⃣ 记忆口诀
完全二叉用数组，下标计算找父母。
一般二叉用链表，左右指针指向清楚。
先序根左右，中序左根右，后序左右根。
7️⃣ 小测验（评论区对答案）
对于一棵深度为h hh的完全二叉树，采用顺序存储时，数组的长度至少为（ ）。
A.h hh
B.2 h − 1 2^{h-1}2h−1
C.2 h − 1 2^h - 12h−1
D.2 h − 2 2^{h} - 22h−2
🔔本专栏日更，点击头像 → 专栏《软考中级高频考点》订阅，第一时间接收新内容
#软考中级 #软件设计师 #二叉树 #顺序存储 #链式存储 #数据结构 #软考备考
