一、二叉树的核心性质
满二叉树的结点数：深度为kkk的满二叉树，其结点总数为2k−12^k - 12k−1。这是因为每一层的结点数为2i−12^{i-1}2i−1（第iii层），从第 1 层到第kkk层求和即得：
∑i=1k2i−1=2k−1 \sum_{i=1}^{k} 2^{i-1} = 2^k - 1i=1∑k2i−1=2k−1终端结点与度 2 结点的关系：在任意二叉树中，设终端结点（叶子）个数为n0n_0n0，度为 2 的结点个数为n2n_2n2，则有：
n0=n2+1 n_0 = n_2 + 1n0=n2+1
推导依据是总边数等于所有结点出度之和，也等于父结点指向孩子的边数。完全二叉树的深度：含有nnn个结点的完全二叉树，其深度为：
⌊log2n⌋+1 \lfloor \log_2 n \rfloor + 1⌊log2n⌋+1
因为前k−1k-1k−1层构成满二叉树结构，最多包含2k−1−12^{k-1}-12k−1−1个结点。
二、二叉树的分类（结合图示）
| 类型 | 定义说明 |
|---|---|
| 满二叉树 | 深度为kkk且总节点数为2k−12^k - 12k−1的二叉树，每一层都达到最大节点数量。例如：深度为 3 的满二叉树有 7 个结点。 |
| 完全二叉树 | 深度为kkk，结点数为nnn，且这些结点对应于深度为kkk的满二叉树中编号为 1 到nnn的结点。特点是除最后一层外，其余层全满；最后一层结点连续靠左排列。 |
| 非完全二叉树 | 不满足“最后一层结点从左到右连续”的条件，如某个内部结点缺少左孩子但存在右孩子，或下层结点中间出现空缺（如图 3-18© 中 6 号结点左侧无兄弟）。 |
三、二叉树的顺序存储结构
存储方式：使用数组按层次遍历顺序（自上而下、自左至右）存放结点，适用于完全二叉树，能高效利用空间并快速计算父子关系。
对于编号为iii的结点（1≤i≤n1 \leq i \leq n1≤i≤n）：
- 双亲结点：若i>1i > 1i>1，其双亲编号为⌊i2⌋\left\lfloor \frac{i}{2} \right\rfloor⌊2i⌋；当i=1i = 1i=1时为根结点，无双亲。
- 左孩子结点：若2i≤n2i \leq n2i≤n，左孩子编号为2i2i2i；否则不存在左孩子。
- 右孩子结点：若2i+1≤n2i+1 \leq n2i+1≤n，右孩子编号为2i+12i+12i+1；否则不存在右孩子。
注：该编号规则基于从 1 开始编号。若编程中使用从 0 开始的数组索引，则需调整公式为：
- 父节点：⌊i−12⌋\left\lfloor \frac{i-1}{2} \right\rfloor⌊2i−1⌋
- 左孩子：2i+12i + 12i+1
- 右孩子：2i+22i + 22i+2
要证明在任意二叉树中，叶子结点（终端结点）个数 $ n_0 $ 与度为 2 的结点个数 $ n_2 $ 满足关系：
n0=n2+1 n_0 = n_2 + 1n0=n2+1
我们可以通过结点总数和边的总数两个角度进行推导。
证明过程
设一棵二叉树中有：
- $ n_0 $：度为 0 的结点数（即叶子结点）
- $ n_1 $：度为 1 的结点数（只有左孩子或右孩子）
- $ n_2 $：度为 2 的结点数（有两个孩子）
则整棵树的总结点数为：
n=n0+n1+n2(1) n = n_0 + n_1 + n_2 \tag{1}n=n0+n1+n2(1)
另一方面，从边的数量来看：
- 每个结点（除根结点外）都由一条边连接到其父结点。
- 所以总的边数为：$ n - 1 $
而这些边也可以通过各结点的出度（孩子数）来计算：
- 度为 1 的结点贡献 1 条边，
- 度为 2 的结点贡献 2 条边，
- 度为 0 的结点贡献 0 条边。
因此，总边数也可表示为：
边数=0⋅n0+1⋅n1+2⋅n2=n1+2n2 \text{边数} = 0 \cdot n_0 + 1 \cdot n_1 + 2 \cdot n_2 = n_1 + 2n_2边数=0⋅n0+1⋅n1+2⋅n2=n1+2n2
又因为边数等于 $ n - 1 $，所以有：
n1+2n2=n−1(2) n_1 + 2n_2 = n - 1 \tag{2}n1+2n2=n−1(2)
将式 (1) 中的 $ n = n_0 + n_1 + n_2 $ 代入式 (2)：
n1+2n2=(n0+n1+n2)−1 n_1 + 2n_2 = (n_0 + n_1 + n_2) - 1n1+2n2=(n0+n1+n2)−1
两边同时减去 $ n_1 $：
2n2=n0+n2−1 2n_2 = n_0 + n_2 - 12n2=n0+n2−1
移项得：
2n2−n2=n0−1⇒n2=n0−1 2n_2 - n_2 = n_0 - 1 \Rightarrow n_2 = n_0 - 12n2−n2=n0−1⇒n2=n0−1
即：
n0=n2+1 n_0 = n_2 + 1n0=n2+1
✅ 得证。
直观理解
这个性质的本质是：每一个新增的“分叉”（即度为 2 的结点）都会增加一个额外的分支路径，从而最终导致多出一个叶子。根结点开始是一个叶子（单节点树），每增加一个度为 2 的结点，相当于把一个叶子变成内部结点，并生成两个新叶子，净增一个叶子。
