本讲定位：官方大纲知识块 1 里点名的三棵树，全在这一讲。真题分布非常稳定：单选第 6 题给一段代码问「这在判断哪种二叉树」、单选第 13 题考 BST 插入填空、判断题每年 2～3 条围绕 BST 性质设陷阱。
更要紧的是：六级编程题第 2 题连续两次就是本讲的内容——2026 年 6 月「数有多少棵子树是满二叉树」、2026 年 3 月「数有多少棵子树是完全二叉树」。25 分，考法几乎一模一样。本讲第 4 节就是专门拆这道题的。
对应官方大纲：六级知识块 1「树」——完全二叉树、二叉排序树。
前置知识：六级第 02 讲（遍历、递归求高度、编号数组存树）。
代码说明：本讲代码均已用 g++ 11.5（
-std=c++11）编译运行验证；子树统计程序与 $n \le 12$ 的暴力枚举对拍 500 组，BST 插入后的中序结果与排序结果对拍 1000 组（含重复值）。
这两个概念最容易混，先把定义摆在一起看。
$$ \boxed{\text{所有叶子深度相同，且除叶子外每个结点都有两个儿子}} $$
这正是 2026 年 6 月六级编程题第 2 题给的官方定义。直观上就是一个完美的三角形：
深度 1： ● 1 个结点
┌──┴──┐
深度 2： ● ● 2 个
┌─┴─┐ ┌─┴─┐
深度 3： ● ● ● ● 4 个
必背公式（设高度为 $h$，根为第 1 层）：
| 量 | 公式 | $h=3$ 时 |
|---|---|---|
| 第 $k$ 层结点数 | $2^{k-1}$ | 第 3 层 4 个 |
| 总结点数 | $2^h - 1$ | $7$ |
| 叶子数 | $2^{h-1}$ | $4$ |
📌 反过来用：总结点数是 $2^h-1$，说明满二叉树的结点数一定是奇数（1, 3, 7, 15, 31, …）。看到偶数个结点，立刻可以判定「不是满二叉树」。
$$ \boxed{\text{除最后一层外都填满，且最后一层的结点全部靠左连续排列}} $$
完全二叉树 ✅ 不是完全二叉树 ❌
1 1
┌──┴──┐ ┌──┴──┐
2 3 2 3
┌─┴─┐ ┌┘ ┌─┘ ┌┘
4 5 6 4 6
↑
第 3 层出现了空隙（5 的位置空着）
满二叉树一定是完全二叉树，反之不然。
结论一：数组下标关系。
$$ \boxed{\text{根在下标 } 0：\ \text{左孩子 } 2i+1,\ \text{右孩子 } 2i+2,\ \text{父亲 } (i-1)/2} $$
完全二叉树可以不用指针，直接用一维数组存，下标连续不留空。这正是它存在的意义。