二叉树常考性质

叶子结点与二分支结点

设非空二叉树中度为 0、1、2 的结点数分别为 $n_0,n_1,n_2$，则：

$$
n_0=n_2+1
$$

推导：

$$
n=n_0+n_1+n_2
$$

又因为树中结点数等于总度数加 1：

$$
n=n_1+2n_2+1
$$

两式相减得 $n_0=n_2+1$。

二叉树第 i 层至多有：

$$
2^{i-1}\quad(i\ge 1)
$$

这是 m 叉树性质在 m=2 时的特例。

高度为 h 的二叉树至多有：

$$
2^h-1
$$

达到上界时是满二叉树。

高度为 h 的二叉树至少有 h 个结点，即每层只有一个结点。

具有 n(n>0) 个结点的完全二叉树高度为：

$$
h=\lceil \log_2(n+1)\rceil
$$

也可写作：

$$
h=\lfloor \log_2 n\rfloor+1
$$

理解方式：

$$
2^{h-1}\le n < 2^h
$$

或：

$$
2^{h-1}-1<n\le 2^h-1
$$

完全二叉树最多只有一个度为 1 的结点，即：

$$
n_1\in{0,1}
$$

又有：

$$
n_0=n_2+1
$$

因此：

记忆突破口：完全二叉树结点按层序连续填充，最后一个结点编号为 n。若 n 是偶数，它是某结点的左孩子，因此存在一个只有左孩子的分支结点；若 n 是奇数，则最后一个结点是右孩子，不会产生度为 1 的结点。

按层序从 1 开始编号时：

这些编号性质只直接适用于完全二叉树；普通二叉树顺序存储时必须先按完全二叉树位置补空位。