4. 满二叉树定理
有些二叉树实现只在 叶结点 中存储数据，
而用 内部结点 来为树提供结构。
根据定义，叶结点不需要存储指向其（空的） 子结点 的指针。
更一般地说，二叉树实现可能需要为内部结点分配一定量的空间，
而为叶结点分配不同的空间量。
因此，为了计算这类实现所需的空间，
知道在包含 \(n\) 个内部结点的树中，
叶结点所占比例的最小值和最大值是很有用的。
遗憾的是，这个比例并不固定。
一棵含 \(n\) 个内部结点的二叉树可能只有一个叶结点。
当内部结点排成一条链、末端是一个叶结点时就会出现这种情况，
如图 12.4.1 所示。
在这个例子中，叶结点的数量很少，因为每个内部结点只有一个非空子结点。
为了求出含 \(n\) 个内部结点的树的叶结点数量上界，
首先要注意，当每个内部结点都有两个非空子结点时，即当树为满二叉树时，
才会达到上界。
然而，这一观察并没有说明什么样的树形会产生最高比例的非空叶结点。
事实证明这无关紧要，因为所有含 \(n\) 个内部结点的满二叉树
都有相同数量的叶结点。
这一事实使我们能够计算一种满二叉树实现所需的空间，
其中叶结点与内部结点所需的空间量不同。
在分析二叉树实现的空间需求时，
知道一棵树包含多少个空子树是很有用的。
满二叉树定理的一个简单推广精确地告诉我们，
任何 二叉树（无论是否为满二叉树）中有多少个空子树。
下面给出证明以下定理的两种方法，
每种方法都提示了一种思考二叉树的有用方式。
