10.1. 二叉树的空间需求¶

本模块介绍根据结点实现方式，计算 二叉树 所需 空间开销 的技术。 回想一下，空间开销是维护数据结构所必需的空间量。 换句话说，它是所有不用于存储数据记录的空间。 空间开销的大小取决于若干因素，包括哪些结点存储数据值 （所有结点，还是只有叶结点）、 叶结点是否存储子结点指针，以及树是否为 满二叉树 。

在一种简单的 基于指针的二叉树结点实现 中，每个结点都有两个指向其子结点的指针（即使子结点为 NULL）。 这种实现为含 \(n\) 个结点的树所需的总空间为 \(n(2P + D)\) 。 这里， \(P\) 表示一个指针所需的空间量， \(D\) 表示一个数据值所需的空间量。 整棵树的总空间开销为 \(2Pn\) 。 因此，空间开销占比为

该表达式的实际值取决于指针相对于数据域的大小。 如果我们随意假设 \(P = D\) ， 那么二叉树总空间中大约有三分之二被空间开销占用。 更糟的是，满二叉树定理告诉我们，大约一半的指针是“浪费”的 NULL 值，它们仅用于指示树结构，而不能提供对新数据的访问。

在许多语言（如 Java 或 JavaScript）中，最典型的实现并不是在结点中 存储实际数据，而是存储一个指向数据记录的指针。 在这种情况下，每个结点通常会存储三个指针，它们都可以视为空间开销， 由此得到的空间开销占比为 \(3P/(3P + D)\) 。 然而，在这种语境下，一种也许更有用的看法是： 每个 容器类都会存储一个指向数据记录的指针， 而我们的目标是比较各种容器实现的相对空间开销。 例如，链表结点为每个结点存储一个纯结构性的空间开销指针， 而二叉树的简单结点实现则存储两个纯结构性的空间开销指针。

如果只有叶结点存储数据值，那么用于空间开销的总空间占比 取决于树是否为满树。 如果树不满，那么可以设想，在一系列内部结点的末端 可能只有一个叶结点。 因此，对于非满二叉树，空间开销可能达到任意高的百分比。 随着树越来越接近满树，空间开销占比会下降， 当树真正为满树时达到最低。 在这种情况下，大约一半的结点是内部结点。

在满二叉树中，消除叶结点的指针可以节省大量空间。 再次假设树中存储的是指向数据域的指针。 由于大约一半的结点是叶结点、一半是内部结点， 而且现在只有内部结点才有子结点指针， 这种情况下空间开销占比大约为

如果 \(P = D\) ，空间开销降到约占总空间的一半。 然而，如果只有叶结点存储有用信息， 那么这种实现的空间开销占比实际上是总空间的 3/4， 因为有一半的“数据”空间未被使用。

如果一棵满二叉树只需在叶结点存储数据， 那么一种更好的实现是让内部结点存储两个指针而不存储数据域， 让叶结点只存储数据域。 这种实现的空间开销占比为

如果 \(P = D\) ，那么空间开销占比为总空间的 \(3P/(3P + D) = 3/4\) 。 空间开销比例上升而总空间量下降，这似乎有违直觉。 原因在于，我们改变了“数据”的定义， 使其仅指存储在叶结点中的内容， 所以尽管空间开销占比更高，但它所基于的总存储需求更低。