这不是概念讲解，全部是选择题/填空题直接套用的数字结论。
每条都带推导，能记住推导就能现场算出来，不靠死背。
已用代码逐一验证，结论可靠。

目录

  1. 树：结点 / 边 / 叶子 / 度数
  2. 二叉树：层 / 深度 / 完全二叉树 / 满二叉树
  3. 二叉链表空指针域 / 线索二叉树
  4. AVL 最少结点（斐波那契）
  5. 哈夫曼树
  6. 卡特兰数（形态数 / 出栈序列 / 括号）
  7. 树与森林转换
  8. 图：边数 / 度数 / 连通性 / 生成树
  9. 线性表：平均移动 / 比较次数
  10. 查找：顺序 / 折半 / 哈希装填因子
  11. 栈 / 队列 / 串 / 广义表
  12. 矩阵压缩存储地址计算
  13. 排序：比较次数下界 / 趟数
  14. 递推公式速记（汉诺塔 / 斐波那契）
  15. 易混易错对照表

一、树：结点 / 边 / 叶子 / 度数

结论 1：n 个结点的树有 n−1 条边

推导：除根结点外，每个结点有且仅有 1 条「父边」指向它。n 个结点中只有根没有父边 → 边数 = n−1。

结论 2（最核心）：任何二叉树 n₀ = n₂ + 1（叶子数 = 度为2的结点数 + 1）

推导（两步）：

  • 设度为 0/1/2 的结点数分别为 n₀、n₁、n₂，总结点数 N = n₀ + n₁ + n₂
  • 「度」按孩子数算，所有结点的度之和 = 边数 = N−1，即 n₁ + 2n₂ = n₀ + n₁ + n₂ − 1
  • 消去 n₁：n₂ = n₀ − 1 → n₀ = n₂ + 1 ✔

结论 3（推广到 m 叉树）：n₀ = 1 + Σ(j−1)·nⱼ（j ≥ 2）

推导：同结论 2，Σ j·nⱼ = N − 1，代入 N = Σ nⱼ 得 n₀ = 1 + n₂ + 2n₃ + 3n₄ + …。

  • 特例：满 k 叉树（所有分支结点度为 k），内部结点数 **n_内 = (n₀−1)/(k−1)**，总结点数 **(k·n₀−1)/(k−1)**。

结论 4：已知各度结点数求叶子/总结点

1
边数 E = N − 1 且 Σ(度×个数) = 2E   ← 本质是图的握手定理

例：二叉树中度 1 的结点 3 个、度 2 的结点 5 个 → 叶子 = 5+1 = 6，总结点 = 3+5+6 = 14。

结论 5：森林有 t 棵树、n 个结点，则边数 = n − t

推导：每棵树 nᵢ 个结点有 nᵢ−1 条边，求和 Σ(nᵢ−1) = n − t。

二、二叉树：层 / 深度 / 完全二叉树 / 满二叉树

结论 1：第 i 层最多 2^(i−1) 个结点

等比数列，第一层 1 个，每层翻倍。

结论 2：深度为 k 的二叉树最多 2^k − 1 个结点

1+2+4+…+2^(k−1) = 2^k − 1。达到上限即满二叉树。

结论 3：n 个结点的二叉树

  • 最少深度（高度）：⌈log₂(n+1)⌉ = ⌊log₂n⌋ + 1（高度最低=接近满二叉树）
  • 最多深度：n（退化为单支链）
  • 反推：高度 h 的二叉树，结点数范围 2^(h−1) ≤ n ≤ 2^h − 1

结论 4：完全二叉树（必考）

设 n 个结点（下标从 1 编号）：

量 结论
深度 ⌊log₂n⌋ + 1
叶子结点数 n₀ ⌈n/2⌉
度为 1 的结点数 n₁ n 为偶 → 1；n 为奇 → 0
最后一个非叶结点编号 ⌊n/2⌋
叶子编号范围 ⌊n/2⌋ + 1 ～ n
结点 i 的父 / 左 / 右 ⌊i/2⌋ / 2i / 2i+1
i 有左孩子 ⟺ 2i ≤ n
i 有右孩子 ⟺ 2i+1 ≤ n

n₁ 的推导：n₀ = ⌈n/2⌉，n₂ = n₀−1，故 n₁ = n − n₀ − n₂ = n − 2⌈n/2⌉ + 1。

  • n 偶 (2m)：n₁ = 2m − 2m + 1 = 1
  • n 奇 (2m+1)：n₁ = 2m+1 − 2(m+1) + 1 = 0

结论 5：满二叉树（深度 k）

  • 结点总数 2^k − 1，叶子 **2^(k−1)**，分支结点 2^(k−1) − 1
  • 叶子数 = 分支结点数 + 1

结论 6：二叉树 n 个结点，恰好只有 n−1 条边（所有树通用），不可能是 n 条

易混点：二叉树的「度」= 孩子数（≤2）；普通树的「度」= 孩子数；图论里「度」= 邻接边数（含父边）。不同上下文别混用。

三、二叉链表空指针域 / 线索二叉树

结论：n 个结点的二叉链表有 n+1 个空指针域

推导：每个结点 2 个指针域，共 2n 个；n−1 条边用掉 n−1 个（每条边=一个孩子指针），空域 = 2n − (n−1) = n+1。

线索二叉树就是利用这 n+1 个空域存前驱/后继 → 线索数 = n+1。

推广：三叉链表（lchild + rchild + parent）

每条边占 2 个指针（一个孩子指针 + 一个父指针），用掉 2(n−1) 个，共 3n 个域 → 空域 = 3n − 2(n−1) = n+2。

四、AVL 最少结点（斐波那契）

结论：高度为 h 的 AVL 树最少结点数满足

1
2
N(h) = N(h−1) + N(h−2) + 1,   N(0)=0, N(1)=1
即   N(h) = Fib(h+2) − 1

数值速查：

高度 h 1 2 3 4 5 6 7
最少结点 1 2 4 7 12 20 33

推导：AVL 树左右子树高度差 ≤ 1，要结点最少，就让左子树高度 h−1、右子树高度 h−2（差 1），再加根结点 → 递推式。解斐波那契即得。

反用：含 n 个结点的 AVL 树最大高度 ≈ 1.44·log₂(n+1)（最坏也 O(log n)）。

五、哈夫曼树

结论：n 个叶子（权值）的哈夫曼树有 2n−1 个结点

推导：每次合并两个结点生成一个新内部结点，合并 n−1 次 → 新增 n−1 个内部结点，总 = n + (n−1) = 2n−1。

其他性质

  • 哈夫曼树没有度为 1 的结点（n₁ = 0）→ n₀ = n₂ + 1 恒成立
  • 权值越小的结点离根越远（编码越长）
  • 哈夫曼编码是前缀编码（任一编码不是另一编码的前缀）
  • WPL = Σ(权 × 路径长度) 最小；权值互异时 WPL 唯一

六、卡特兰数（形态数 / 出栈序列 / 括号）

公式：Cₙ = C(2n, n) / (n+1)

数值速查：1, 1, 2, 5, 14, 42, 132, 429, 1430…

四大应用（考到就是这几种）

  1. n 个结点的二叉树形态数
  2. n 个元素进栈，可能的出栈序列数
  3. n 对括号的合法匹配数
  4. 凸 n+2 边形三角剖分数（即 Cₙ）

记忆推导：把二叉树的左右子树递归拆分，Tₙ = Σ Tₖ·Tₙ₋₁₋ₖ，解出封闭式 C(2n,n)/(n+1)。

例：3 个结点二叉树形态 = C₃ = 5（✓ 符合常识）。

七、树与森林转换

转换 结论
树 → 二叉树 结点数不变；根结点的右子树必为空（根没有兄弟）
森林 t 棵树 → 二叉树 结点数不变；二叉树的根即第一棵树的根
森林边数 n − t（见第一节结论 5）
还原判定 二叉树根无右孩子 ⟹ 对应一棵树；根有右孩子 ⟹ 对应森林

八、图：边数 / 度数 / 连通性 / 生成树

结论 1：握手定理

  • 无向图：Σ(顶点度) = 2E，故度之和必为偶数 → 奇度顶点个数必为偶数
  • 有向图：Σ入度 = Σ出度 = E

结论 2：完全图边数（必考）

图 边数
无向完全图 Kₙ n(n−1)/2
有向完全图（每对顶点两条有向边） n(n−1)
完全二分图 K(a,b) a·b

推导：Kₙ 每两点连一条边 = 从 n 个点取 2 个组合数 C(n,2) = n(n−1)/2。

结论 3：连通性最少边数（高频易混，务必分清）

问题 最少边数
n 顶点无向图恰好连通（构造出来连通） n−1
n 顶点有向图恰好强连通 n（构成一个大环，每点入=出=1）
n 顶点无向图保证无论怎么连都连通 C(n−1,2) + 1
n 顶点有向图（忽略方向）弱连通 n−1

「保证连通」推导：最坏情况是 n−1 个顶点先构成完全图（C(n−1,2) 条边）把第 n 个顶点孤立，再加 1 条边连它 → 任何连线方式下都必然连通。

例：n=5 → 4 个顶点完全图 6 条 + 1 = 7 条（✓ 已验证）。

结论 4：生成树

  • 连通图 n 顶点 m 条边 → 生成树恰有 n−1 条边
  • 完全图 Kₙ 的生成树个数 = **n^(n−2)**（Cayley 公式）

    K₃ → 3 棵，K₄ → 16 棵

结论 5：平面图（欧拉公式）

  • 连通平面图：V − E + F = 2（F 为面数）
  • 简单平面图必有 E ≤ 3V − 6；无三角形则 E ≤ 2V − 4
  • 推论：K₅、K₃,₃ 都是非平面图

结论 6：欧拉图

  • 存在欧拉回路 ⟺ 连通且所有顶点度为偶
  • 存在欧拉通路（不回起点）⟺ 连通且恰有 0 或 2 个奇度顶点
  • 有向欧拉回路 ⟺ 入度 = 出度（且连通）

结论 7：二分图 ⟺ 无奇环 ⟺ 2-可着色

结论 8：拓扑排序成功 ⟺ 无环（DAG）；序列唯一 ⟺ 每步入度为 0 的顶点恰一个

九、线性表：平均移动 / 比较次数

结论 1：顺序表插入/删除平均移动次数（高频！）

操作 平均移动次数
在长度为 n 的顺序表插入（n+1 个位置） n/2
删除（n 个位置） (n−1)/2
无序查找（比较次数） (n+1)/2

插入推导：在第 i 个位置插入需移动 n−i+1 个，平均 = Σ(n−i+1)/(n+1) = [n+(n−1)+…+0]/(n+1) = n(n+1)/2 ÷ (n+1) = n/2。
删除推导：平均 = Σ(n−i)/n = (n−1)/2。

结论 2：链表插入/删除

  • 已知位置指针 → O(1)；已知值 → 需先 O(n) 查找，总体 O(n)。
  • 无头结点 vs 有头结点：头插/头删在有头结点时统一逻辑。

十、查找：顺序 / 折半 / 哈希装填因子

结论 1：顺序查找

  • 成功 ASL = (n+1)/2；失败 ASL = n+1（比较到末尾再+哨兵）

结论 2：折半查找（基于有序数组）

  • 最多比较 ⌊log₂n⌋ + 1 次（判定树高度）
  • 成功 ASL ≈ log₂(n+1) − 1（n = 2^k − 1 满判定树时精确）
  • 比较次数与元素值无关，只取决于位置（判定树）。

结论 3：哈希表

  • 装填因子 α = 表中元素个数 n / 表长 m
  • 线性探测：成功 ASL ≈ (1/2)(1 + 1/(1−α))；失败 ASL ≈ (1/2)(1 + 1/(1−α)²)
  • 链地址法：成功 ASL ≈ 1 + α/2
  • α 越大冲突越多；α > 0.75 时冲突急剧上升（这也是 HashMap 0.75 的由来）

十一、栈 / 队列 / 串 / 广义表

栈

  • n 个元素进栈，出栈序列数 = 卡特兰数 Cₙ（见第六节）
  • 例：3 个元素进栈有 C₃ = 5 种出栈序列

队列（循环队列，容量 M，头 front 尾 rear）

  • 元素个数 = (rear − front + M) % M
  • 判空 front == rear；判满 (rear+1) % M == front（留一个空位）
  • 判满推导：不留空位的话 front==rear 无法区分空与满（状态数 2^? 表示冲突）

串

  • 长度为 n 的串，子串个数 = n(n+1)/2 + 1（含 1 个空串）；非空子串 = n(n+1)/2
  • KMP：O(n+m)；朴素匹配最坏 O(n·m)
  • next 数组 = 失配时最长公共前后缀长度

广义表

  • 长度 = 最外层元素个数；深度 = 括号最大嵌套层数
  • 表头 = 第一个元素；表尾 = 除第一个元素外的子表

十二、矩阵压缩存储地址计算（填空必考）

对称矩阵 A[1..n][1..n] 行优先压缩存一维 B

下三角（含对角线）元素总数 = n(n+1)/2。
A[i][j]（i ≥ j）存到 B 的 1-based 下标 k = i(i−1)/2 + j
推导：前 i−1 行共 1+2+…+(i−1) = i(i−1)/2 个元素，第 i 行第 j 列是第 j 个 → k = i(i−1)/2 + j。

  • 若 k 从 0 计：k = i(i−1)/2 + j − 1
  • 上三角元素 A[i][j]（i<j）用对称性查 A[j][i]

三角矩阵

  • 下三角 + 常数 = n(n+1)/2 + 1

三对角矩阵（带宽 1）

  • 元素总数 = 3n − 2（第 1、n 行各 2 个，中间 n−2 行各 3 个）

稀疏矩阵

  • 三元组表存储：(行, 列, 值)，空间 O(非零元素个数)
  • 十字链表适合动态修改

十三、排序：比较次数下界 / 趟数

结论 1：比较排序下界 Ω(n log n)

推导：n 个元素有 n! 种排列，比较排序的决策树是二叉的，区分所有排列至少需要高度 ≥ ⌈log₂(n!)⌉，而 log₂(n!) = n log₂ n − 1.44n ≈ n log₂ n。
→ 归并/快排/堆排的 O(n log n) 就是理论最优（常数内）。

例：n=8 → 至少 ⌈log₂ 8!⌉ = ⌈15.3⌉ = 16 次比较。

结论 2：趟数 / 比较次数速记

排序 趟数 最坏比较次数 平均比较次数
冒泡 ≤ n−1 n(n−1)/2 n(n−1)/2
插入 n−1 n(n−1)/2 n²/4
选择 n−1 n(n−1)/2 n(n−1)/2
快排 递归树高度 n(n−1)/2（基本有序） ≈ 1.39n log n
归并 log n 层 n log n n log n
堆排 n−1 n log n n log n

结论 3：稳定排序 = 插、冒、归、基（口诀「插冒归基」）

结论 4：已基本有序 → 插入排序最优（O(n)）；内存不够 → 外部归并

十四、递推公式速记（汉诺塔 / 斐波那契）

递推 结果 推导要点
汉诺塔 T(n) = 2T(n−1) + 1 2^n − 1 先把 n−1 盘移走 + 移大盘 + 再移回
斐波那契 递归 O(2^n) T(n)=T(n−1)+T(n−2)，指数爆炸
斐波那契 迭代/矩阵 O(n) / O(log n) 滚动变量；矩阵快速幂
AVL 最少结点（第五节） Fib(h+2) − 1 N(h)=N(h−1)+N(h−2)+1
归并 T(n)=2T(n/2)+O(n) O(n log n) 每层 O(n)，log n 层
二分 T(n)=T(n/2)+O(1) O(log n) 每次折半

十五、易混易错对照表

易混点 正确答案 错误答案（避坑）
n 个结点树边数 n−1 n
二叉树叶子与度为2 n₀ = n₂ + 1 n₀ = n₂
完全二叉树叶子 ⌈n/2⌉ ⌊n/2⌋（相差在 n 为奇时）
完全二叉树 n₁ 奇→0，偶→1 恒为 0
二叉链表空域 n+1 2n
三叉链表空域 n+2 n+1
恰好连通最少边 n−1 C(n−1,2)+1（那是”保证”）
保证连通最少边 C(n−1,2)+1 n−1（那是”恰好”）
有向强连通最少边 n n−1
无向完全图边数 n(n−1)/2 n(n−1)（那是有向）
顺序表插入平均移动 n/2 (n−1)/2（那是删除）
折半查找最多比较 ⌊log₂n⌋+1 log₂n（差 1，n 非 2 幂时别取整错）
哈夫曼总结点数 2n−1 n（忽略内部结点）
完全二叉树深度 ⌊log₂n⌋+1 ⌈log₂(n+1)⌉（两者相等，别混）
比较排序下界 Ω(n log n) O(n log n)（那是上界/平均）

附录：一句话推导精华（考前 5 分钟）

  1. 边数 n−1：除根外每点一条父边。
  2. n₀=n₂+1：Σ度 = N−1。
  3. 完全二叉树叶子 ⌈n/2⌉：满树叶子最多，去掉下层右半边。
  4. 空链域 n+1：2n − (n−1)。
  5. AVL 最少结点：左高 h−1 + 右高 h−2 + 1 = 斐波那契。
  6. 哈夫曼 2n−1：n−1 次合并。
  7. **卡特兰 C(2n,n)/(n+1)**：左右子树递归拆分。
  8. 握手定理 Σ度=2E：每条边贡献 2。
  9. 保证连通 C(n−1,2)+1：最坏 n−1 点全连接 + 1 条边。
  10. 顺序表插入 n/2、删除 (n−1)/2：等差求和平均。
  11. 折半 ⌊log₂n⌋+1：判定树高度。
  12. α = n/m：装填因子。
  13. 循环队列 (rear−front+M)%M。
  14. 对称矩阵 k = i(i−1)/2 + j。
  15. 比较排序下界 n log n：决策树 n! 种排列。

所有数字结论均已用程序验证。考前把「十五、易混易错表」和「附录」过一遍即可。