树的递归定义#

树（Tree）是 n（n ≥ 0）个结点的有限集合。当 n = 0 时称为空树；当 n > 0 时，满足以下条件：

1. 有且仅有一个称为根（Root）的结点
2. 其余结点可分为 m（m > 0）个互不相交的有限集合 T₁, T₂, …, Tₘ，每个集合本身又是一棵树，称为根的子树（Subtree）

这个递归定义是理解树所有操作的基础——树的算法几乎天然适合用递归实现。

基本术语#

注意：考研 408 中，“深度”和”高度”是站在不同角度定义的。深度从根往下数（根为 1），高度从叶子往上数（叶子为 0 或 1）。部分教材将叶子高度定义为 1，做题时以题目说明为准，但 408 统考倾向于高度 = 最大层数。

树的性质#

1. 树中结点数 = 所有结点的度数之和 + 1
2. 度为 m 的树中第 i 层上至多有 m^(i-1) 个结点（i ≥ 1）
3. 高度为 h 的 m 叉树至多有 (m^h - 1) / (m - 1) 个结点（满 m 叉树）
4. 具有 n 个结点的 m 叉树的最小高度为 ⌈log_m(n(m-1) + 1)⌉

二叉树的重要特征#

• 每个结点最多有 2 棵子树（度 ≤ 2）
• 左右子树严格区分，顺序不能颠倒
• 二叉树不是度为 2 的有序树的特例——二者的区别在于：二叉树允许结点最多有 2 棵子树（可以为 0 或 1 棵），而度为 2 的有序树要求结点恰好有 2 棵子树（度为 0 或 1 的结点不符合定义）。因此二叉树是比度为 2 的有序树更一般的结构。

特殊二叉树#

性质一：结点数与度数的关系#

n₀ = n₂ + 1 （叶子结点数 = 度为 2 的结点数 + 1）

证明：设 n₀、n₁、n₂ 分别表示度为 0、1、2 的结点数，总结点数 n = n₀ + n₁ + n₂。从边的角度看，每条边对应一个非根结点：边数 = n - 1 = 0·n₀ + 1·n₁ + 2·n₂。联立两式得 n₀ = n₂ + 1。

⚠️ 考研超高频考点：n₀ = n₂ + 1 几乎在每年的 408 真题中出现。可用于：已知叶子结点数求度为 2 的结点数，或反过来求。注意该性质只适用于二叉树。

性质二：完全二叉树的结点数关系#

• n₁ 只能为 0 或 1（当总结点数为奇数时 n₁ = 1，偶数时 n₁ = 0）
• 第 i 个结点的双亲编号为 ⌊i/2⌋（i > 1）
• 第 i 个结点的左孩子编号为 2i（2i ≤ n），右孩子编号为 2i+1（2i+1 ≤ n）

性质三：空指针域#

具有 n 个结点的二叉树，用二叉链表存储时，空指针域数量为 n + 1。

证明：n 个结点的二叉链表共有 2n 个指针域，但只有 n-1 条边（非空指针），所以空指针数 = 2n - (n-1) = n + 1。这个性质是线索二叉树的基础——线索二叉树正是利用这些空指针存放前驱和后继信息。

顺序存储#

用一维数组按完全二叉树的顺序存放结点：

1
下标: [1] [2] [3] [4] [5] [6] [7] ...
2
结点:  a   b   c   d   e   f   g  ...

下标规则：

• 结点 i 的左孩子：2i
• 结点 i 的右孩子：2i + 1
• 结点 i 的双亲：⌊i/2⌋

适用场景：完全二叉树和满二叉树。普通二叉树会造成大量空间浪费（需要补充空结点到完全二叉树形式）。

考研关键点：顺序存储的下标从 1 开始更常见，但有些题目可能从 0 开始。从 0 开始时，左孩子为 2i+1，右孩子为 2i+2。

链式存储#

二叉链表（最常用）：

1
typedef struct BiTNode {
2
    int data;
3
    struct BiTNode *lchild, *rchild;
4
} BiTNode, *BiTree;

1
       [data]
2
      /      \
3
  lchild    rchild

三叉链表（增加 parent 指针，便于回溯）：

1
typedef struct TriTNode {
2
    int data;
3
    struct TriTNode *lchild, *rchild, *parent;
4
} TriTNode, *TriTree;

两种存储结构对比#