二叉树、二叉排序树、完全二叉树与堆全解秒杀模型

【学长导读】 本卡片彻底解决 408 考生对“树形结构形态规则与关键字偏序混淆”的痛点。 结合 2020 年第 3 题、第 5 题、第 9 题与第 10 题,将二叉树家族、堆、AVL 树、以及外存大杀器 B 树/B+ 树一网打尽。

🔗 高分双链直达:


一、二叉树与多路平衡树家族“进化大一统”知识链

所有常考树形结构,本质上都是从一棵没有任何规则的“野生二叉树”开始,**叠加不同维度的约束(几何形态约束、数值偏序约束、平衡性约束、外存多路扩展、带权路径)**进化而来的:

进化逻辑链条深度拆解:

  1. 几何形态约束链:
    • 野生二叉树(每个结点最多度 ) 约束“从上到下、自左向右连续报数” 完全二叉树 (CBT);
    • 完全二叉树 约束“最后一排也全部坐满” 满二叉树 (Full BT)()。
  2. 数值全序与平衡进化链(内存查找 外存查找):
    • 野生二叉树 约束“左小右大” 二叉排序树 (BST)(中序遍历单调递增,但输入有序时会退化为单支树 );
    • BST 约束“左右子树高度差绝对值 ” 平衡二叉树 (AVL)(查找稳定 );
    • AVL 树走向 B 树 / B+ 树的工程宿命:
      • 二叉平衡树在内存中表现优异,但在磁盘(外存)大规模数据检索中,由于每个结点仅有两个分叉,树高 依然很深,每一次向下深入都会触发一次昂贵的磁盘 I/O 随机寻道!
      • 为减少磁盘 I/O,必须**“以宽度换高度,将树压扁矮胖化”**,将二叉扩展为 叉平衡树 B 树 (Balance Tree);
      • 为进一步优化范围查询与文件系统扫表,将非叶结点纯化为索引、所有真实数据沉淀至底层叶结点并用双向链表相连 B+ 树。
  3. 特种功能树链:
    • 完全二叉树骨架 + 堆序性(纵向父子偏序) 大/小根堆 (Heap)(Top-K 极值秒出,天然适配一维紧凑数组);
    • 叶结点带权 + 带权路径长度 WPL 最小 哈夫曼树 (Huffman Tree)(,,最优前缀编码)。

二、满二叉树 vs 完全二叉树:本质区别与精准辨析

很多同学做题混淆,是因为把“形态规则”和“连续编号”搞混了。学长用直观图解和生活场景定格画面:

1. 形象通俗比喻

  • 满二叉树 “座无虚席的豪华剧院”:
    • 从 1 楼到顶楼,每一个座位都坐满了人。只要缺了哪怕一个人、留了一个空位,就立刻丧失叫“满”的资格。
  • 完全二叉树 “早操报数队伍(严格靠左无空隙)”:
    • 前面 排全部站满;
    • 最后一排可以站满,也可以不站满;但关键是:所有人必须按学号从最左边一个挨着一个向右站齐,中间绝不能有人旷课留出‘空位’!

2. 本质区别与考点判定对比表

对比维度满二叉树 (Full Binary Tree)完全二叉树 (Complete Binary Tree)
底层核心定义高为 的二叉树,结点总数严格等于 编号为 的结点与满二叉树编号 完全一一对应
最后一层形态最后一层(第 层)必须全满,不能有任何空缺最后一层可以不满,但存在的结点必须严格靠左连续排列
度为 1 的结点数 ()严格为 0(每个非叶结点必定有左右两个孩子)只能是 0 或 1(最多只有 1 个结点只有左孩子,绝不可能只有右孩子)
叶子结点分布只能分布在最底层(第 层)只能分布在最底两层(第 层和第 层)
存储结构亲和度顺序、链式皆可一维数组顺序存储的天花板选手(下标无间隙,0 空间碎片)
从属包含关系满二叉树必定是完全二叉树(满二叉树是完全二叉树的极端特例)完全二叉树不一定是满二叉树

3. 完全二叉树必背“四大神级公式”(408 每年必考)

若一棵完全二叉树有 个结点(按层序从 到 连续编号):

  1. 树的高度 :
  2. 父子相对寻址定位(无需指针,下标硬算):
    • 结点 的双亲结点编号:(当 时无双亲,为根)。
    • 结点 的左孩子编号:(若 ,说明无左孩子,为叶子结点)。
    • 结点 的右孩子编号:(若 ,说明无右孩子)。
  3. 最后一个非叶子结点:
    • 编号恰好是 (这是堆排序建堆时自底向上筛选的起点!)。
  4. 叶子结点的总数:

三、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+ 树!


关联高分知识卡片