10.4. 满二叉树定理¶

有些二叉树实现只在 叶结点 中存储数据，而用 内部结点 来为树提供结构。根据定义，叶结点不需要存储指向其（空的） 子结点 的指针。更一般地说，二叉树实现可能需要为内部结点分配一定量的空间，而为叶结点分配不同的空间量。因此，为了计算这类实现所需的空间，知道在包含 \(n\) 个内部结点的树中，叶结点所占比例的最小值和最大值是很有用的。

遗憾的是，这个比例并不固定。一棵含 \(n\) 个内部结点的二叉树可能只有一个叶结点。当内部结点排成一条链、末端是一个叶结点时就会出现这种情况，如图 10.4.1 所示。在这个例子中，叶结点的数量很少，因为每个内部结点只有一个非空子结点。为了求出含 \(n\) 个内部结点的树的叶结点数量上界，首先要注意，当每个内部结点都有两个非空子结点时，即当树为满二叉树时，才会达到上界。然而，这一观察并没有说明什么样的树形会产生最高比例的非空叶结点。事实证明这无关紧要，因为所有含 \(n\) 个内部结点的满二叉树都有相同数量的叶结点。这一事实使我们能够计算一种满二叉树实现所需的空间，其中叶结点与内部结点所需的空间量不同。

在分析二叉树实现的空间需求时，知道一棵树包含多少个空子树是很有用的。满二叉树定理的一个简单推广精确地告诉我们， 任何 二叉树（无论是否为满二叉树）中有多少个空子树。下面给出证明以下定理的两种方法，每种方法都提示了一种思考二叉树的有用方式。