二叉平衡树的结点数计算

问题分析

若二叉树平衡树的高度为 h，那么该树有多少个节点？

二叉平衡树与完全二叉树一样，不能根据 h 求出确切的节点数，只能求出一个上界和下界。

最小节点的情况是：平衡因子不为 0，也就是说，如果某一个子树的高度为 n，那么另一颗子树的高度一定为 n - 1.

于是我们就可以通过如下的递推式求出最小节点数，其中 $v_{h}$ 表示高度为 h 的最小节点：

\begin{aligned} v_{0} = 0, \\ v_{1} = 1, \\ \dots \\ v_{h} = 1 + v_{h - 1} + v_{h - 2} \end{aligned}

即该平衡二叉树为满二叉树的情况，那么节点数（根节点在第一层）显然为：

v_{h} = 2^{n - 1}