二叉树、二叉排序树、完全二叉树与堆全解秒杀模型
【学长导读】 本卡片彻底解决 408 考生对“树形结构形态规则与关键字偏序混淆”的痛点。 结合 2020 年第 3 题、第 5 题、第 9 题与第 10 题,将二叉树家族、堆、AVL 树、以及外存大杀器 B 树/B+ 树一网打尽。
🔗 高分双链直达:
- 平衡二叉树专项突破:平衡二叉树(AVL)插入与旋转调整全解秒杀模型
- B 树动态插入与删除调整:B树删除与调整规则全题型秒杀笔记
一、二叉树与多路平衡树家族“进化大一统”知识链
所有常考树形结构,本质上都是从一棵没有任何规则的“野生二叉树”开始,**叠加不同维度的约束(几何形态约束、数值偏序约束、平衡性约束、外存多路扩展、带权路径)**进化而来的:
进化逻辑链条深度拆解:
- 几何形态约束链:
- 野生二叉树(每个结点最多度 ) 约束“从上到下、自左向右连续报数” 完全二叉树 (CBT);
- 完全二叉树 约束“最后一排也全部坐满” 满二叉树 (Full BT)()。
- 数值全序与平衡进化链(内存查找 外存查找):
- 野生二叉树 约束“左小右大” 二叉排序树 (BST)(中序遍历单调递增,但输入有序时会退化为单支树 );
- BST 约束“左右子树高度差绝对值 ” 平衡二叉树 (AVL)(查找稳定 );
- AVL 树走向 B 树 / B+ 树的工程宿命:
- 二叉平衡树在内存中表现优异,但在磁盘(外存)大规模数据检索中,由于每个结点仅有两个分叉,树高 依然很深,每一次向下深入都会触发一次昂贵的磁盘 I/O 随机寻道!
- 为减少磁盘 I/O,必须**“以宽度换高度,将树压扁矮胖化”**,将二叉扩展为 叉平衡树 B 树 (Balance Tree);
- 为进一步优化范围查询与文件系统扫表,将非叶结点纯化为索引、所有真实数据沉淀至底层叶结点并用双向链表相连 B+ 树。
- 特种功能树链:
- 完全二叉树骨架 + 堆序性(纵向父子偏序) 大/小根堆 (Heap)(Top-K 极值秒出,天然适配一维紧凑数组);
- 叶结点带权 + 带权路径长度 WPL 最小 哈夫曼树 (Huffman Tree)(,,最优前缀编码)。
二、满二叉树 vs 完全二叉树:本质区别与精准辨析
很多同学做题混淆,是因为把“形态规则”和“连续编号”搞混了。学长用直观图解和生活场景定格画面:
1. 形象通俗比喻
- 满二叉树 “座无虚席的豪华剧院”:
- 从 1 楼到顶楼,每一个座位都坐满了人。只要缺了哪怕一个人、留了一个空位,就立刻丧失叫“满”的资格。
- 完全二叉树 “早操报数队伍(严格靠左无空隙)”:
- 前面 排全部站满;
- 最后一排可以站满,也可以不站满;但关键是:所有人必须按学号从最左边一个挨着一个向右站齐,中间绝不能有人旷课留出‘空位’!
2. 本质区别与考点判定对比表
| 对比维度 | 满二叉树 (Full Binary Tree) | 完全二叉树 (Complete Binary Tree) |
|---|---|---|
| 底层核心定义 | 高为 的二叉树,结点总数严格等于 | 编号为 的结点与满二叉树编号 完全一一对应 |
| 最后一层形态 | 最后一层(第 层)必须全满,不能有任何空缺 | 最后一层可以不满,但存在的结点必须严格靠左连续排列 |
| 度为 1 的结点数 () | 严格为 0(每个非叶结点必定有左右两个孩子) | 只能是 0 或 1(最多只有 1 个结点只有左孩子,绝不可能只有右孩子) |
| 叶子结点分布 | 只能分布在最底层(第 层) | 只能分布在最底两层(第 层和第 层) |
| 存储结构亲和度 | 顺序、链式皆可 | 一维数组顺序存储的天花板选手(下标无间隙,0 空间碎片) |
| 从属包含关系 | 满二叉树必定是完全二叉树(满二叉树是完全二叉树的极端特例) | 完全二叉树不一定是满二叉树 |
3. 完全二叉树必背“四大神级公式”(408 每年必考)
若一棵完全二叉树有 个结点(按层序从 到 连续编号):
- 树的高度 :
- 父子相对寻址定位(无需指针,下标硬算):
- 结点 的双亲结点编号:(当 时无双亲,为根)。
- 结点 的左孩子编号:(若 ,说明无左孩子,为叶子结点)。
- 结点 的右孩子编号:(若 ,说明无右孩子)。
- 最后一个非叶子结点:
- 编号恰好是 (这是堆排序建堆时自底向上筛选的起点!)。
- 叶子结点的总数:
三、2020 年统考真题全景联动透视(第 3、5、9、10 题连环拳)
408 命题组在 2020 年试卷中,顺着物理存储 逻辑构建 偏序关系 外存多路树层层设伏:
1. 第 3 题:二叉树顺序存储物理映射与最大下标
- 真题情境:高度为 5 且有 10 个结点的任意二叉树,顺序存储至少要多少存储单元?
- 破题关键:
- 题目给的是普通二叉树,不是完全二叉树!
- 顺序存储为了维护父子映射规则(左孩子 ,右孩子 ),缺失的空位必须留出单元占位。
- 数组容量只取决于“整棵树结点的最大可能下标”,与结点总数 10 无关!
- 题干“任意一棵”要求必须容纳最极端情况(右单支树),第 5 层的右下单支叶子下标直达满二叉树极限 。
- 结论:选 A(31)。
2. 第 5 题:二叉排序树 BST 的动态构建
- 真题情境:判断哪个关键字输入序列不能生成指定的二叉排序树。
- 破题关键:
- BST 规则:左小右大,序列第一个元素先入为主成为根。
- 目标树形态:根 4,左孩子 2,右孩子 5;2 的左孩子 1,右孩子 3。
- 序列
4, 5, 1, 2, 3中:4 成为根后,紧接着 1 来了,此时 4 的左子树还是空的,1 会直接落成 4 的左孩子,2 随后只能沦为 1 的右孩子,形态彻底跑偏! - 结论:选 B。
3. 第 9 题:大根堆的本质(完全二叉树 + 堆序性)
- 真题情境:判断大根堆的性质(逻辑结构、顺序存储、BST 关系、次大值位置)。
- 破题关键:
- 堆的骨架是完全二叉树 I 正确;
- 因为是完全二叉树,所以最适合顺序存储 II 正确;
- 堆是纵向父子偏序(只管上下),左右兄弟毫无大小制约;而 BST 是严格横向全序(左 < 根 < 右) 堆绝不是 BST,III 错误;
- 大根堆根最大,次大值必定在第 2 层(左孩子或右孩子) IV 正确。
- 结论:选 C(仅 I、II、IV)。
4. 第 10 题:4 阶 B 树的动态构建与分裂
- 真题情境:依次插入
5, 6, 9, 13, 8, 2, 12, 15,求根结点的关键字。 - 破题关键:
- 4 阶 B 树结点最多容纳 个关键字,达到 4 个即上溢分裂。
- 分裂提取第 个关键字(偏右中位数)上升入父结点。
- 插入 13 时
[5, 6, 9, 13]分裂,9 上升成根;插入 2 时左子树[2, 5, 6, 8]满,提 6 上升并入根,根变成[6, 9]。 - 结论:选 B(6, 9)。
- 👉 详细分裂图解与删除全流程直达:B树删除与调整规则全题型秒杀笔记
四、408 常考 8 大树形结构终极横向对比大表
| 树形结构 | 核心形态约束 | 关键字偏序/数值特征 | 首选存储结构 | 核心考点公式 / 复杂度 | 典型命题人陷阱 |
|---|---|---|---|---|---|
| 满二叉树 | 每一层结点数均达上限,无空缺 | 无特定数值大小约束 | 顺序 或 链式 | 高度 ,结点数 ;叶子全在第 层 | 误将完全二叉树当成满二叉树 |
| 完全二叉树 | 编号与满二叉树 一一对应,底层靠左对齐 | 无特定数值大小约束 | 顺序存储(一维数组) 无缝紧凑存储 | 高度 ;叶子数 ;最后非叶结点 | 误以为普通二叉树顺序存储省空间;普通树单支退化最坏需 空间 |
| 二叉排序树 (BST) | 形态无强制约束(随输入序列动态决定) | 左子树 < 根 < 右子树 (中序遍历严格单调递增) | 链式存储(二叉链表) | 最好查找 ;若输入有序则退化为单支树,最坏查找 | 误以为堆也是 BST;误以为 BST 的中序遍历需要特别额外排序 |
| 平衡二叉树 (AVL) | 在 BST 基础上增加:任一结点左右子树高度差绝对值 | 保持 左 < 根 < 右 | 链式存储 (需维护平衡因子 bf) | 高度为 的最少结点数递推式: () | 旋转调整考点:LL/RR 单旋、LR/RL 双旋的判断及旋转后的新根选取 |
| 大/小根堆 (Heap) | 严格必须是完全二叉树 | 父子有序,左右无序 (大根堆:根 孩子;小根堆:根 孩子) | 顺序存储(一维数组) | 最大/小值在下标 1;次值在下标 2 或 3;建堆复杂度 ,单次调整 | 误以为堆的左右孩子有大小关系;误以为建堆时间是 |
| 哈夫曼树 (最优树) | 只有度为 0 和度为 2 的结点(不存在度为 1 的结点 ) | 仅叶结点带权值,从叶到根带权路径长度 WPL 最小 | 静态链表(数组存储一维结构体) | 个叶子对应哈夫曼树总节点数必为 ;非叶节点数必为 | 误以为哈夫曼树形态唯一(左右可调换,相同权值合并顺序不同形态可变,但 WPL 唯一) |
| B 树 (多路平衡树) | 叉平衡树,所有叶子结点在同一层;非根结点关键字数 | 关键字与子树交叉有序;非叶结点既存索引也存真实记录指针 | 节点内顺序表 + 动态孩子指针 | 树高范围 ;节点分叉 | 混淆子树数与关键字数(子树数永远比关键字数多 1);忘了所有叶子在同层 |
| B+ 树 (外存与数据库) | 叉树,非叶结点只存索引不存数据;所有叶子构成单/双向链表 | 叶子包含全部关键字与记录;非叶结点的每个关键字对应一棵子树( 个关键字对应 棵子树) | 节点内索引数组 + 底层链表 | 极度支持范围查询与顺序扫描;单次查询磁盘 I/O 稳定等于树高 | 混淆 B 树与 B+ 树的子树对应关系(B树关键字比子树少1,B+树关键字数等于子树数) |
五、考场秒杀口诀总结
看形态:
满树层层满座席,完全靠左无缝隙;
普通树用数组存,最大下标准备齐 ()!看数值:
BST 管左中右(中序升序),堆管上下不管旁;
二叉平衡太瘦高,外存压扁找 B 树;
叶子链表全数据,范围查询 B+ 树!