二叉树的五条核心性质

以下性质默认非空二叉树，根结点层次为 1。

性质 1：第 $i$ 层最多有 $2^{i-1}$ 个结点

• 证明：第 1 层最多 1 个（$2^0$），第 2 层最多 2 个（$2^1$），……，第 $i$ 层最多 $2^{i-1}$ 个。

性质 2：深度为 $h$ 的二叉树最多有 $2^h - 1$ 个结点

• 证明：各层最多结点数之和：$2^0 + 2^1 + \dots + 2^{h-1} = 2^h - 1$。
• 注意：当树为满二叉树时达到最大值。

性质 3：对任意二叉树，若叶子结点数为 $n_0$，度为 2 的结点数为 $n_2$，则 $n_0 = n_2 + 1$

• 证明：设总结点数 $n = n_0 + n_1 + n_2$，总分支数（边数）$B = n - 1 = n_1 + 2n_2$。两式联立消去 $n$ 得 $n_0 = n_2 + 1$。

性质 4：具有 $n$ 个结点的完全二叉树深度为 $\lfloor \log_2 n \rfloor + 1$

• 证明：设深度为 $h$，则 $2^{h-1} \le n < 2^h$，取对数得 $h-1 \le \log_2 n < h$，故 $h = \lfloor \log_2 n \rfloor + 1$。

性质 5（完全二叉树结点编号规律）：按层序编号（从 1 开始）

对编号为 $i$ 的结点：

• 若 $i = 1$，为根；否则双亲编号为 $\lfloor i/2 \rfloor$。
• 若 $2i \le n$，则左孩子编号为 $2i$；否则无左孩子。
• 若 $2i+1 \le n$，则右孩子编号为 $2i+1$；否则无右孩子。

这是数组存储完全二叉树的理论基础。

总结表

性质	公式	用途
第 i 层最多结点数	$2^{i-1}$	求满二叉树某层结点
深度 h 最多结点数	$2^h - 1$	判断满二叉树
叶子与度为 2 的关系	$n_0 = n_2 + 1$	已知一种求另一种
完全二叉树深度	$\lfloor \log_2 n \rfloor + 1$	计算深度
结点编号关系	双亲、孩子编号公式	顺序存储实现