2.2.2 Hierarchical Structures

The representation of sequences in terms of lists generalizes naturally to

represent sequences whose elements may themselves be sequences. For example,

we can regard the object ((1 2) 3 4) constructed by

将序列表示为表的方式自然地推广到这样一种序列：其元素本身也可以是序列。例如，可以将由以下方式构造的对象 ((1 2) 3 4)

as a list of three items, the first of which is itself a list, (1 2).

Indeed, this is suggested by the form in which the result is printed by the

interpreter. Figure 2.5 shows the representation of

this structure in terms of pairs.

Figure 2.5: Structure formed by (cons (list 1 2) (list 3 4)).

视为一个包含三个元素的表，其中第一个元素本身是一个表 (1 2)。事实上，解释器打印结果的形式本身就暗示了这一点。图 2.5 展示了该结构用序对表示的方式。

图 2.5：由 (cons (list 1 2) (list 3 4)) 构成的结构。

Another way to think of sequences whose elements are sequences is as

将元素本身也是序列的序列看作

trees. The elements of the sequence are the branches of the tree,

and elements that are themselves sequences are subtrees. Figure 2.6

shows the structure in Figure 2.5 viewed as a tree.

Figure 2.6: The list structure in Figure 2.5 viewed as a tree.

树 (trees) 是另一种思考方式。序列中的各元素是树的分支，而那些本身也是序列的元素则是子树。图 2.6 展示了图 2.5 中的结构以树的视角来看的样子。

图 2.6：图 2.5 中的表结构作为树来看。

Recursion is a natural tool for dealing with tree structures, since we can

often reduce operations on trees to operations on their branches, which reduce

in turn to operations on the branches of the branches, and so on, until we

reach the leaves of the tree. As an example, compare the length

procedure of 2.2.1 with the count-leaves procedure, which

returns the total number of leaves of a tree:

递归是处理树形结构的天然工具，因为我们往往可以将对树的操作规约为对其分支的操作，再进一步规约为对分支的分支的操作，如此递推，直至到达树的叶节点。作为例子，将 2.2.1 节中的 length 过程与 count-leaves 过程加以比较——后者返回一棵树中叶节点的总数：

To implement count-leaves, recall the recursive plan for computing

length:

要实现 count-leaves，回忆计算 length 的递归方案：

Length of a list x is 1 plus length of the

cdr of x.

表 x 的长度等于 1 加上 x 的 cdr 的长度。

Length of the empty list is 0.

Count-leaves is similar. The value for the empty list is the same:

Count-leaves of the empty list is 0.

空表的长度为 0。

count-leaves 与之类似。空表对应的值相同：

空表的 count-leaves 为 0。

But in the reduction step, where we strip off the car of the list, we

must take into account that the car may itself be a tree whose leaves we

need to count. Thus, the appropriate reduction step is

但在归约步骤中，当我们剥去表的 car 时，必须考虑到 car 本身可能也是一棵树，其叶节点也需要计数。因此，适当的归约步骤为

Count-leaves of a tree x is count-leaves of the car

of x plus count-leaves of the cdr of x.

Finally, by taking cars we reach actual leaves, so we need another base

case:

Count-leaves of a leaf is 1.

树 x 的 count-leaves 等于 x 的 car 的 count-leaves 加上 x 的 cdr 的 count-leaves。

最终，不断取 car 将到达真正的叶节点，因此还需要另一个基础情况：

叶节点的 count-leaves 为 1。

To aid in writing recursive procedures on trees, Scheme provides the primitive

predicate pair?, which tests whether its argument is a pair. Here is

the complete procedure:

为了便于编写操作树的递归过程，Scheme 提供了基本谓词 pair?，用于测试其实参是否为序对。以下是完整的过程：