3. 树的顺序表示¶
3.1. 树的顺序表示¶
接下来我们考虑一种实现树的根本不同的方法。 其目标是用重建树结构所需的最少信息来存储一系列结点值。 这种方法称为 顺序表示 ， 它的优点是节省空间，因为不存储指针。 它的缺点是，访问树中任意结点都需要按顺序处理结点线性表中 出现在它之前的所有结点。 换句话说，结点访问必须从结点线性表的开头开始， 按照结点存储的顺序依次处理，直到到达所需的结点。 因此，本节讨论的其他实现的一个主要优点就丧失了： 对树中任意结点的高效访问（通常是 \(\Theta(\log n)\) 时间）。 顺序表示实现非常适合把树归档到磁盘上以备后用， 因为它们节省空间，并且可以在需要时重建树结构以供后续处理。
顺序表示实现可以用来 序列化 树结构。 序列化是把对象存储为一系列字节的过程， 通常是为了让数据结构能够在计算机之间传输。 在分布式处理环境中使用数据结构时，这种能力很重要。
顺序表示实现通常按照前序遍历枚举的顺序存储结点值， 并附带足以描述树形结构的信息。 如果树具有受限的形式，例如它是一棵满二叉树， 那么通常需要存储的结构信息就更少。 一般树由于形状最为灵活，往往需要最多的额外形状信息。 可能的顺序表示实现方案有很多。 我们将先描述适用于二叉树的方法， 再推广到适用于一般树结构的实现。
由于二叉树的每个结点要么是叶结点，要么有两个（可能为空的）子结点， 我们可以利用这一事实来隐式地表示树的结构。 最直接的顺序表示实现会按照前序遍历枚举的顺序列出每一个结点值。 遗憾的是，仅凭结点值不足以恢复树的形状。 特别是，当我们读取这一系列结点值时，并不知道何时到达了叶结点。 不过，我们可以把所有非空结点都视为有两个（可能为空的）子结点的 内部结点。 只有 NULL 值会被解释为叶结点，而这些值可以显式列出。 这样一份扩充后的结点线性表提供了足以恢复树结构的信息。
3.2. 另一种顺序表示¶
为了说明使用顺序表示进行处理所涉及的困难， 请考虑查找根结点的右子结点。 我们必须先顺序遍历左子树的结点线性表。 只有到这时才会到达根结点右子结点的值。 显然，顺序表示在空间上是高效的， 但在沿某条任意路径向下遍历树时，它在时间上并不高效。
假设每个结点值占用常数量的空间。
一个例子是：结点值为正整数，而 null 用值零表示。
由 满二叉树定理 可知，
结点线性表的长度大约是结点数目的两倍（即空间开销比例为 1/2）。
额外的空间是由 null 指针所需的。
我们应当能够更紧凑地存储结点线性表。
然而，任何顺序表示实现都必须能识别何时到达了叶结点，
也就是说，叶结点表示一棵子树的结束。
做到这一点的一种方法是，为每个结点显式列出它是内部结点还是叶结点。
如果结点 \(X\) 是内部结点，
那么我们知道它的两个子结点（可能是子树）紧跟在结点线性表中
\(X\) 的后面。
如果 \(X\) 是叶结点，那么线性表中的下一个结点是 \(X\) 的
某个祖先的右子结点，而不是 \(X\) 的右子结点。
具体来说，下一个结点将是 \(X\) 最近一个尚未见到其右子结点的
祖先的子结点。
然而，这假定每个内部结点确实都有两个子结点，换句话说，树是满的。
空子结点必须在结点线性表中显式标出。
假设内部结点用撇号（'）标记，叶结点不显示标记。
内部结点的空子结点用 "/" 表示，
但叶结点的（空）子结点则完全不表示。
注意，在这种实现下，满二叉树不存储任何 null 值，
因此所需的空间开销更少。
存储 \(n\) 个额外的二进制位比存储 \(n\) 个 null 值
要节省相当多空间。
在上面的例子中，每个结点如果内部结点就显示一个标记，
如果是叶结点则不显示标记。
这要求每个结点值都有空间来存储标记位。
例如，如果结点值存储为 4 字节整数，但所存储值的范围足够小，
以至于并非所有二进制位都被用到，这就可能成立。
一个例子是所有结点值都必须为正数。
这样，整数值的高阶（符号）位就可以用作标记位。
3.3. 位向量表示¶
另一种方法是存储一个单独的位向量来表示每个结点的状态。 在这种情况下，树中的每个结点对应位向量中的一位。 值 "1" 可以表示内部结点， "0" 可以表示叶结点。
3.4. 一般树的顺序表示¶
用顺序表示实现来存储一般树，要求在结点线性表中包含更多显式的 结构信息。 一般树实现不仅要指出一个结点是叶结点还是内部结点， 还必须指出该结点有多少个子结点。 另一种做法是，实现可以指出一个结点的子结点线性表何时结束。 下一个例子不再使用内部结点或叶结点的标记。 相反，它包含一个特殊标记（我们将使用 ")" 符号） 来表示一个子结点线性表的结束。 所有叶结点后面都跟一个 ")" 符号，因为它们没有子结点。 一个同时也是其父结点最后一个子结点的叶结点， 会用两个或更多连续的 ")" 符号来表示这一点。
注意，这种用于序列化一般树的表示不能用于二叉树。 这是因为二叉树并不仅仅是一种至多有两个子结点的一般树的受限形式。 每个二叉树结点都有一个左子结点和一个右子结点，尽管其中一个或两个 可能为空。 所以这种表示无法让我们区分图 13.3.1 中的 结点 \(D\) 是结点 \(B\) 的左子结点还是右子结点。
