7.10.1. 二叉树的空间需求¶

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

在一种简单的 基于指针的二叉树结点实现（pointer-based implementation for binary tree nodes） 中，每个结点都有两个指向其子结点的指针（即使子结点为 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\) 。空间开销比例上升而总空间量下降，这似乎有违直觉。原因在于，我们改变了“数据”的定义，使其仅指存储在叶结点中的内容，所以尽管空间开销占比更高，但它所基于的总存储需求更低。