一、树的基本概念
1. 树的定义与性质
- 树是 n (n≥0) 个结点的有限集合。n=0 时为空树。
- 非空树有且仅有一个根结点，其余结点可分为 m 个互不相交的有限集，每个集合本身又是一棵树（子树）。
- 树中每个结点最多只有一个直接前驱（双亲），可以有多个直接后继（孩子）。
- 结点的度：该结点拥有的子结点个数。
- 树的度：树内各结点度的最大值。
2. 树中结点数与度的关系（通用公式）
设树中结点总数为 n，度为0的结点数为 n₀，度为1的结点数为 n₁，…，度为 k 的结点数为 nₖ，则有：
总结点数 = 所有结点度数之和 + 1 即：n = 0×n₀ + 1×n₁ + 2×n₂ + … + k×nₖ + 1
示例（第5题）：度为3的树中，度为3的结点2个，度为2的结点1个，度为1的结点2个，求度为0的结点数。
- 代入公式：n = 3×2 + 2×1 + 1×2 + 1 = 6+2+2+1 = 11
- 又 n = n₀ + n₁ + n₂ + n₃ = n₀ + 2 + 1 + 2 = n₀ + 5
- 所以 n₀ = 11 - 5 = 6。
3. k叉树的最大与最小深度
- 含有 n 个结点的 k 叉树：
- 最大深度：n（每层只有一个结点，单支树）。
- 最小深度：
⌈logₖ(n(k-1)+1)⌉，对于满 k 叉树约为⌊logₖn⌋+1。 - 对于二叉树（k=2）：最小深度为
⌈log₂(n+1)⌉或⌊log₂n⌋+1。
二、二叉树的核心性质
1. 二叉树定义
- 每个结点最多两棵子树（度≤2），且子树有左右之分，次序不能任意颠倒。
2. 二叉树的5条基本性质
| 性质 | 内容 |
|---|---|
| 性质1 | 第 i 层上至多有 2ⁱ⁻¹ 个结点（i≥1） |
| 性质2 | 深度为 k 的二叉树至多有 2ᵏ - 1 个结点 |
| 性质3 | 任意二叉树：终端结点数 n₀ = 度为2的结点数 n₂ + 1 |
| 性质4 | n 个结点的完全二叉树深度为 ⌊log₂n⌋ + 1 |
| 性质5 | 完全二叉树按层编号：i 的双亲为 ⌊i/2⌋，左孩子为 2i，右孩子为 2i+1（i=1 起始） |
3. 性质3推导（叶子与二分支结点关系）
- 总结点数 n = n₀ + n₁ + n₂
- 总分支数 = n - 1 = n₁ + 2n₂
- 两式联立得：n₀ = n₂ + 1
应用示例（第25题）：双分支结点15，单分支结点30，叶子数 = 15 + 1 = 16。
4. 满二叉树 vs 完全二叉树
- 满二叉树：深度为 k 且有 2ᵏ-1 个结点，每层都是满的，不存在度为1的结点。
- 完全二叉树：除最后一层外，其余层都是满的，且最后一层结点从左向右连续排列。
- 完全二叉树中，若一个结点没有左孩子，则它必定是叶结点（因为编号不连续）。
- 完全二叉树的叶子结点只可能出现在最下两层。
5. 完全二叉树的深度计算
深度 =
⌊log₂n⌋ + 1
示例：35个结点，log₂35 ≈ 5.13，⌊5.13⌋=5，深度=6；257个结点，log₂257≈8.00，⌊8⌋=8，深度=9。
6. 完全二叉树的结点计算（叶子、度为2、度为1）
- 设完全二叉树结点总数为 n：
- 若 n 为偶数，则 n₁ = 1（最后一个分支结点只有左孩子），n₀ = n/2。
- 若 n 为奇数，则 n₁ = 0（没有单分支结点），n₀ = (n+1)/2。
- 无论奇偶，n₂ = n₀ - 1。
示例（第26题）：700个结点（偶数），叶子数 = 700/2 = 350。
示例（第31题）：1000个结点（偶数），叶子 = 1000/2 = 500，度为2的结点 = 500-1 = 499。由于 n 为偶数，n₁ = 1，即只有一个结点只有非空左子树，无非空右子树的情况。
7. 二叉树的不同形态数
- 3个结点的二叉树共有 5种 形态（2个结点2种，1个结点1种）。
- 给定先序序列为 ABC 的不同二叉树：由卡特兰数 C₃=5，也是5种。
三、二叉树的遍历（重点）
1. 三种遍历的定义
| 遍历方式 | 操作顺序 |
|---|---|
| 先序（前序） | 根 → 左子树 → 右子树 |
| 中序 | 左子树 → 根 → 右子树 |
| 后序 | 左子树 → 右子树 → 根 |
2. 遍历的重要性质
- 叶子结点在先序、中序、后序序列中的相对次序不发生改变（都是从左到右）。
- 中序序列中，A在B前的条件是 A 在 B 的左方（A是B左子树中的结点，或B是A右子树中的结点）。
- 若二叉树采用二叉链表，交换所有分支结点左右子树，用后序遍历最合适（先交换左右子树，再回到双亲）。
3. 由遍历序列推导二叉树（必考通用方法）
唯一确定二叉树的条件：
- 已知 先序 + 中序 → 唯一确定。
- 已知 后序 + 中序 → 唯一确定。
- 已知 先序 + 后序 → 不能唯一确定（真二叉树除外）。
通用步骤（以先序+中序为例）：
- 从先序序列第一个字符确定根结点。
- 在中序序列中找到该根，左边为左子树的中序序列，右边为右子树的中序序列。
- 根据左子树结点个数，回到先序序列划分出左、右子树的先序序列。
- 对左右子树递归重复。
示例1（第2题）：先序 ABCDEFG，中序 CBAEDFG。
- 根：A。
- 中序：A左边 CB → 左子树有B、C；右边 EDFG → 右子树有D、E、F、G。
- 左子树先序 BC，中序 CB → 根B，B左孩子C；右子树先序 DEFG，中序 EDFG → 根D，D左子树E（中序E在D前），右子树FG。
- 逐步构建后序：C B E G F D A → 答案应为 CBEGFDA。
示例2（第16题）：先序 ABCDEF，中序 CBAEDF，求后序。
- 根A，左子树中序CB → 先序BC；右子树中序EDF → 先序DEF。
- 左子树根B，中序C在B左 → B左C；右子树根D，中序E在D左，F在D右 → D左E右F。
- 后序：C B E F D A。
示例3（第21题）：后序 DABEC，中序 DEBAC，求先序。
- 从后序末位定根：根C。
- 中序C左边 DEBA，右边空。
- 左子树后序 DABE，根E；中序 D E BA → E左D，右BA。
- 右子树后序 AB，根B；中序 B A → B左A。
- 先序：C E D B A → CEDBA。
4. 特殊遍历条件下的推断
- 若某二叉树先序与中序序列相同，则所有结点只有右子树（无左孩子），即右单支树（此时先序=中序）。
- 先序 ABCDEFG 中序可能是 ABCDEFG，符合此情况。
四、二叉树存储结构
1. 顺序存储
- 适用于完全二叉树，按层序编号存入数组（下标从1或0开始）。
- 一般二叉树用顺序存储会浪费空间。
2. 链式存储（二叉链表）
- 每个结点包含：左孩子指针、右孩子指针、数据域。
- 在二叉链表中，根结点的右指针为空（因为根无兄弟，孩子兄弟表示法中右指针才指兄弟）。
3. 树的存储形式（非二叉树）
- 双亲表示法、孩子链表表示法、孩子兄弟表示法（二叉链表表示法）。
- 树的顺序存储表示法不是常用存储形式，因树结构不规则。
五、易错填空题公式速记
| 问题 | 通用公式/结论 |
|---|---|
| 完全二叉树深度 | ⌊log₂n⌋ + 1 |
| 完全二叉树叶子数（n偶） | n/2 |
| 完全二叉树叶子数（n奇） | (n+1)/2 |
| 度为2结点数 | n₀ - 1 |
| 满二叉树深度为k的分支结点数 | 2ᵏ⁻¹ - 1 |
| 满二叉树深度为k的叶子数 | 2ᵏ⁻¹ |
| 3个结点二叉树形态数 | 5 |
| n个结点k叉树最大深度 | n |
| n个结点k叉树最小深度 | ⌈logₖ(n(k-1)+1)⌉，二叉树为⌊log₂n⌋+1 |
六、知识速记卡
- 性质3是计算核心：n₀ = n₂ + 1，终端结点永远比双分支结点多1。
- 完全二叉树：深度用⌊log₂n⌋+1；叶子数取决于奇偶；若缺左孩子则必是叶子。
- 遍历推导：先序+中序或后序+中序可唯一确定二叉树；先序+后序不行。
- 遍历性质：叶子结点的相对顺序在所有遍历中不变；中序前后关系=左右位置关系。
- 存储：二叉链表根右指针为空；树的存储有双亲、孩子链表、孩子兄弟三种。