二叉树的性质

性质1

$n$ 二叉树的第 $i$ 层上最多有 $2^{i-1}$ 个节点。($i \ge 1$)
提问：第 $i$ 层上至少有 $1$ 个节点。

性质2

深度为 $h$ 的二叉树最多有 $2^h-1$ 个节点。($h \ge 1$)
提问：一颗深度为 $k$ 且有 $2^k-1$ 个节点的二叉树称为满二叉树。
提问：深度为 $k$ 时至少有 $k$ 个节点（形成一条链）。

性质3

对于任何一颗二叉树，如果其叶子节点数为 $n_0$，度为 $2$ 的节点数为 $n_2$，则一定满足：$n_0 = n_2+1$。

证明：
$边数=点数-1$
$边数=度为二的节点（对应两条边 缩写为 n_1）* 2 + 度为一的节点个数（对应一条边 缩写为 n_2） * 1$
$n = n_2*2+n_1*1+1 = n_0+n_1n+n_2$（$n$ 表示点一共的数量）
进行移项）
得出：$n=n_2+1=n_0$
一颗完全二叉树有 $5000$ 个节点，可以计算出其叶子节点的数量是 $2500$。
RT，$n_1=1$（5000是奇数，于是有一个度为 $1$ 的节点。

$$n_0+n_1+n_2=n_0+1+n_2=n_0+1+n_0-1\\ =2n_0 = 5000 2n_0=2500$$

性质4

具有 $n$ 个节点的完全二叉树的深度为 $\lfloor \log_2 n \rfloor +1 $ 。
证明：

$$2^{k-1}-1 \le n \le 2^k-1\\ （比上一层多，当前这层少）\\ 2^{k-1} \le n < 2^k\\ k-1 \le \log_2 n < k\\ 所以：\lfloor \log_2 n \rfloor +1$$

性质5

对于一颗有 $n$ 个节点的完全二叉树，对任意一个节点 $i$ ,如果 $i=1$,则该节点为根，没有父节点，如果 $i>1$，其父节点编号为 $\lfloor i/2 \rfloor$。
如果 $2i>n$，则该节点没有子节点，即节点 $i$ 为叶子节点；否则左孩子编号为 $2i$。
如果 $2i+1>n$，则该节点没有右孩子；否则右孩子编号为 $2i+1$。