13.3.3 树与二叉树的特性-02

本节继续讲二叉树性质，核心是两个关系：叶子节点数与度为 2 的节点数关系，以及二叉链表中的空指针个数。课程多次强调，用小例子代入能比死记更稳。

度为 0、1、2 的节点

二叉树中节点的度只可能是 0、1、2。记：

记号	含义
$n_0$	度为 0 的节点数，也就是叶子节点数
$n_1$	度为 1 的节点数
$n_2$	度为 2 的节点数
$n$	总节点数

显然：

$$n=n_0+n_1+n_2$$

为什么 $n_0=n_2+1$

从边数角度看，一棵有 $n$ 个节点的树有 $n-1$ 条分支。另一方面，所有节点贡献的分支数等于它们的度之和：

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

又因为：

$$n=n_0+n_1+n_2$$

联立可得：

$$n_0=n_2+1$$

这条性质非常高频。它说明叶子节点数只由度为 2 的节点数决定，与度为 1 的节点数无关。

二叉链表的空指针个数

二叉链表中每个节点有两个孩子指针，所以 $n$ 个节点一共有：

$$2n$$

个孩子指针。其中真实指向孩子节点的指针数等于边数：

$$n-1$$

因此空指针数为：

$$2n-(n-1)=n+1$$

课程用例子验证：只有 1 个节点时，有 2 个空孩子；有 2 个节点时，有 3 个空孩子，都满足 $n+1$。

层数与节点数的范围

如果二叉树高度为 $h$：

情况	节点数
最少	$h$，单支树
最多	$2^h-1$，满二叉树

因此若题目说“高度为 $h$ 的二叉树有多少节点”，单一数值通常不对，除非题目问最多或最少。

节点数为 $n$ 时的高度范围

节点数固定为 $n$：

情况	高度
最小高度	尽量填成完全二叉树，约为 $\lfloor {\log }_{2}n\rfloor +1$
最大高度	单支树，高度为 $n$

注意这里是“最小高度”，不是所有二叉树高度都等于该值。

做性质题的两种方法

方法	适用场景
公式推导	题目问一般关系，如 $n_0,n_1,n_2$
小例子验证	选择题中判断选项真假，快速找反例

例如问“有 $k$ 个节点的二叉树空孩子指针有多少”，用 $k=1$ 验证：空指针为 2，排除 $k$、$k-1$ 等选项，再用 $k=2$ 验证可得到 $k+1$。

本节例题

单选

含有 $n$ 个节点的二叉链表中，空孩子指针个数为：

AnBn-1C2nDn+1

自查清单

1. 能否推导 $n_0=n_2+1$？
2. 能否解释二叉链表空指针为什么是 $n+1$？
3. 能否区分“高度为 $h$ 的最多节点数”和“节点数为 $n$ 的最小高度”？