9.1.1. 引言¶

现在我们着手解决为一般树设计实现的问题，使模块 <GenTreeIntro> 中 ADT 的所有成员函数都能得到高效的处理。 本节介绍实现一般树的几种方法。 每种实现在存储一个结点所需的空间量，以及关键操作执行的相对难易程度上， 各有其优点和缺点。 一般树的实现不应限制一个结点可以拥有的孩子数量。 在某些应用中，结点一旦创建，孩子的数量就再也不会改变。 在这种情况下，可以根据结点的孩子数量，在创建结点时为其分配固定大小的空间。 如果可以向结点添加或删除孩子，事情就变得复杂了， 因为需要相应地调整结点的空间分配。

9.1.2. 子结点链表¶

我们实现一般树的第一次尝试称为一般树的"子结点链表"实现。 它简单地在每个内部结点中存储其孩子的链表。 如图 27.9.1 所示。

"子结点链表"实现把树的结点存储在一个数组中。 每个结点包含一个值、一个指向其父结点的指针（或下标）， 以及一个指向该结点孩子链表的指针，孩子按从左到右的顺序存储。 链表的每个元素包含一个指向某个孩子的指针。 因此，一个结点最左边的孩子可以直接找到，因为它是链表中的第一个元素。 然而，要找到一个结点的右兄弟就比较困难了。 考虑结点 \(M\) 及其父结点 \(P\) 的情况。 要找到 \(M\) 的右兄弟，我们必须沿着 \(P\) 的孩子链表向下移动， 直到找到存储指向 \(M\) 的指针的那个链表元素。 再往后走一步，就到达存储指向 \(M\) 右兄弟的指针的链表元素。 因此，在最坏情况下，要找到 \(M\) 的右兄弟， 必须搜索 \(M\) 的父结点的所有孩子。

如果每棵树都存储在单独的结点数组中，那么用这种表示法合并树就很困难。 如果两棵树的结点存储在同一个结点数组中， 那么把树 \(\mathbf{T}\) 添加为结点 \(R\) 的子树， 只需简单地把 \(\mathbf{T}\) 的根结点添加到 \(R\) 的孩子链表中即可。

9.1.3. 左孩子/右兄弟实现¶

在"子结点链表"实现中，访问结点的右兄弟很困难。 图 27.9.2 给出了一种改进。 这里，每个结点存储其值以及指向其父结点、最左孩子和右兄弟的指针。 这样，每个基本 ADT 操作都可以通过直接从结点读取一个值来实现。 如果两棵树存储在同一个结点数组中， 那么把一棵树添加为另一棵树的子树只需设置三个指针。 以这种方式合并树如图 27.9.3 所示。 这种实现比"子结点链表"实现更节省空间， 并且结点数组中的每个结点所需的空间量是固定的。

9.1.4. 动态结点实现¶

刚才描述的两种一般树实现都使用数组来存储结点集合。 相比之下，我们实现二叉树的标准做法是，把每个结点存储为独立的动态对象， 包含其值和指向其两个孩子的指针。 遗憾的是，一般树的结点可以有任意数量的孩子， 而且这个数量在结点的生命周期内可能会改变。 一般树结点的实现必须支持这些性质。 一种解决方案是简单地限制每个结点允许的孩子数量， 并只为这个确切的数量的孩子分配指针。 这种做法有两个主要的反对理由。 首先，它对孩子数量施加了一个不理想的限制， 使得某些树无法用这种实现来表示。 其次，这可能极度浪费空间，因为大多数结点的孩子会远少于这个数量， 从而留下一些空的指针位置。

另一种做法是为每个结点分配可变空间。 有两种基本方法。 一种是在结点中分配一个孩子指针数组。 本质上，每个结点存储一个基于数组的孩子指针表。 图 27.9.4 说明了这一概念。 这种方法假定在创建结点时孩子的数量已知， 这对某些应用成立，但对另一些应用不成立。 如果孩子的数量不变，这种方法的效果也最好。 如果孩子的数量确实会改变（尤其是增加）， 就必须提供某种特殊的回收机制，以支持孩子指针数组大小的变化。 一种可能的方式是从空闲存储中分配一个大小合适的新结点， 并把该结点的旧副本归还给空闲存储以供以后重用。 这在具有内置垃圾收集功能的语言（如 Java）中效果尤其好。 例如，假设结点 \(M\) 最初有两个孩子， 并且在创建 \(M\) 时为两个孩子指针分配了空间。 如果向 \(M\) 添加第三个孩子，就可以为有三个孩子指针的新结点分配空间， 把 \(M\) 的内容复制到新空间，然后把旧空间归还给空闲存储。 除了依赖系统的垃圾收集器之外， 还可以为可变大小的存储单元实现一个内存管理器， 如 Memory Management 章所述。 另一种可能是使用一组空闲链表，每个数组大小一个， 如模块 <Freelist> 所述。 注意在图 27.9.4 中， 每个结点当前孩子的数量显式地存储在一个 size 字段中。 孩子指针存储在一个含有 size 个元素的数组中。

另一种方法更灵活，但需要更多空间， 它是在每个结点中存储一个孩子指针链表， 如图 27.9.5 所示。 这种实现本质上与"子结点链表"实现相同， 只是结点是动态分配的，而不是存储在数组中。

9.1.5. 动态左孩子/右兄弟实现¶

"左孩子/右兄弟"实现为每个结点存储固定数量的指针。 这可以很容易地改造成动态实现。 本质上，我们是用一棵二叉树来代替一般树。 "左孩子/右兄弟"实现的每个结点，在新二叉树结构中指向两个"孩子"。 这个新结构的左孩子是结点在一般树中的第一个孩子。 右孩子是结点的右兄弟。 我们可以很容易地把这种转换推广到一般树的森林， 因为树的根结点可以被视为兄弟结点。 把一般树的森林转换为一棵二叉树， 如图 27.9.6 所示。 这里，我们只需保留从每个结点指向其右兄弟的链接， 并删除除最左孩子以外的所有孩子的链接。 图 27.9.7 展示了这在每个结点有两个指针的实现中是什么样子。 与图 27.9.5 所示的实现相比 （该实现需要每结点三个指针的开销）， 图 27.9.7 的实现每个结点只需两个指针。 图 27.9.7 的表示很可能比本节介绍的其他实现 更易于实现、更节省空间，也更为灵活。