高度为 $k$ 的二项树恰有 $2^k$ 个结点.
证明:
二项树 $B_k$, 以二项树 $B_0,B_1,B_2,\ldots,B_{k-1}$ 作为其根的儿子. (其中 $B_j$ 指高度为 $j$ 的二项树.
高度为 $k$ 的二项树恰有 $2^k$ 个结点, 在深度 $d$ 处的结点数是二项系数 $\binom{k}{d}$.
Answer
问题及解答
1
二项树是通过递归方法来定义的.
(1) 高度为零的树是指单结点构成的树.
(2) 高度为 $k$ 的二项树 $B_k$ 是通过将一棵二项树 $B_{k-1}$ 附接到另一棵二项树 $B_{k-1}$ 的根上而构成.
(3) 要求是根值大的树其根结点接到根值小的树的根结点上.
高度为零的二项树是单结点树 $B_0$. 高度为 $1$ 的树 $B_1$ 是由两棵高度为 $0$ 的树拼接而来. 因此 $B_1$ 的根结点有一个子树 $B_0$. 如果再附接一棵子树 $B_1$ 就得到高度为 $2$ 的二项树 $B_2$.
因此可以假设对于高度为 $k$ 的二项树 $B_k$ 来说, 结论都成立, 即以二项树 $B_0,B_1,\ldots,B_{k-1}$ 作为其根的儿子.
现在考虑高度为 $k+1$ 的二项树 $B_{k+1}$. 由于它是两棵高度为 $k$ 的二项树 $B_k$ 拼接而来, 因此有额外一个子树 $B_k$, 去掉此子树, 就变为高度为 $k$ 的二项树, 符合归纳假设. 因此 $B_{k+1}$ 以二项树 $B_0,B_1,\ldots,B_{k-1}, B_k$ 作为其根的儿子.