问题及解答

Def. 对于二叉树, 满结点(full node)是指具有两个儿子的结点.

应用.

若某二叉树有 20 个叶子结点, 有 30 个结点仅有一个儿子, 则该二叉树的总的结点数是多少?

(用归纳法证明) 这里设二叉树总共有 $N$ 个结点, 其中有 $m$ 个满结点. 树叶的个数是 $\ell$ 个. 仅有一个儿子的结点数是 $N-m-\ell$.

当 $N=1$ 时, 仅有根结点. 此时 $m=0$, $\ell=1$(根结点就是叶子), 故结论成立.

当 $N=2$ 时, 根结点仅有一个儿子, 此时 $m=0$, $\ell=1$, 结论也成立.

当 $N=3$ 时, 二叉树要么高度是 1, 要么高度是 2. 对于高度是 1 的二叉树, $m=1$, $\ell=2$. 对于高度是 2 的二叉树, $m=0$, $\ell=1$.

现在假设结论对于 $N=k$ 成立. 当考虑具有 $k+1$ 个结点的二叉树时, 任意取一个叶子结点 $p$, 去掉这个叶子结点的二叉树具有 $k$ 个结点, 根据归纳假设, 它的满结点个数加上 1 等于叶子结点数.

我们观察这个叶子结点 $p$, 如果它的父结点不是满结点(也即只有一个儿子), 则原二叉树去掉叶子结点 $p$ 后, 并未改变满结点的个数, 也未改变叶子结点的个数(尽管少了 $p$, 但是 $p$ 的父结点成了叶子).

如果 $p$ 的父结点是满结点, 则原二叉树去掉叶子结点 $p$ 后, 少了一个满结点, 但同时叶子结点也少了一个.

因此结论对于 $N=k+1$ 个结点的二叉树仍然成立.

(法二)

设二叉树有 $N$ 个结点, 其中满结点、树叶以及仅有一个儿子的结点的个数分别是 $m,\ell, s$. 则

\[
m+\ell+s=N\tag{1}
\]

从另一个角度看, 每个结点带有两个指针, 于是二叉树共有 $2N$ 个指针, 其中非空指针(即存储实际地址, 确实指向其他结点的)有 $N-1$ 个. 空指针(即取 NULL 值)个数是 $N+1$. (参见问题1071)

于是, 得到方程

\[
2m+0\cdot\ell+1\cdot s=N-1\tag{2}
\]

(1)-(2), 得

\[-m+\ell=1\]

即 $\ell=m+1$, 也就是说, 满结点个数加上一等于叶子结点的个数.