层次结构——小写 t 树

小写 t 树概览

我们来讨论小写 t 树的一些基本性质。我们已经知道，像 (cons (list 1 2) (list 3 4)) 这样的结构可以表示成树形结构：

小写 t 树由分支（branch）和叶子（leaf）组成。上面的树有五条分支，它们对应上图中从左向右的连线。请注意，一条分支可以通向一棵子树（subtree）——即包含在更大树中的树。在本例中，分支 ((1 2) 3 4) 包含子树 (1 2)。叶子没有从它连出的分支。上面的树有 4 个叶子：1、2、3 和 4。叶子位于树的”底部”，也称为 fringe（边缘）。

与现实世界中的树相比，计算机科学里的树往往是倒过来的！

用递归处理小写 t 树

处理树时，用递归（recursion）的方式思考通常很有帮助。举个例子，我们来写一个函数 count-leaves，统计一棵树中有多少个叶子。

我们先用平实的英语粗略描述这个函数要做什么，这称为编写伪代码（pseudocode）。在理解了 count-leaves 应有的行为之后，我们再为它编写真正的 Racket 代码。这是解决问题的好习惯。

伪代码

回顾我们如何定义 length——它统计列表中的元素个数：

• 空列表的 length 是 0。
• 非空列表 x 的 length 是 1 加上 x 的 cdr 的 length。

count-leaves 的基本情况（base case）与此相同：

• 空列表的 count-leaves 是 0。

但递归情况略有不同。在 length 中，我们保证列表的 car 是单个元素，所以它的长度计为 1。而对于 count-leaves，它的 car 可能包含一棵或多棵子树，其长度并不总是 1。因此，我们还需要递归地求树的 car 的 count-leaves！于是我们的递归调用是：

• 一棵树的 count-leaves 等于这棵树的 car 的 count-leaves 加上其 cdr 的 count-leaves。

最终我们会一路 car 到树的叶子，于是有第二个基本情况：

• 一个叶子的 count-leaves 是 1。

pair? 谓词

对一棵树调用 car 时，我们必须判断它返回的是另一棵树（一个序对），还是一个叶子（单个元素，技术上称为原子 atom）。如何检查？Racket 提供了内置谓词 pair?，测试其参数是否为 cons 的结果。例如：

• (pair? (cons 1 2)) 返回 #t。
• (pair? (cons 1 (cons 2 3))) 返回 #t。
• (pair? 2) 返回 #f。
• (pair? 'pear) 返回 #f。
• (pair? '()) 返回 #f。

真正的代码

借助 pair? 和上面的伪代码，我们可以写出 count-leaves 的完整代码：

(define (count-leaves x)
    (cond ((null? x) 0) ;; 树是空的吗？
          ((not (pair? x)) 1) ;; 树是单个元素吗？
          (else (+ (count-leaves (car x)) ;; 否则，对 car 调用 count-leaves
                   (count-leaves (cdr x)))))) ;; 再对 x 的 cdr 调用，然后相加

示例：scale-tree

在第 4 课中，我们见过函数 scale-list，它把列表中的每个元素乘以一个给定的数值因子。现在我们要写一个类似的函数 scale-tree，它接受一个深列表和一个数值因子，把深列表中的所有元素都乘以该因子。

示例调用如下：

> (scale-tree (list 1 (list 2 (list 3 4) 5) (list 6 7)) 10)
(10 (20 (30 40) 50) (60 70))

测试理解

下面是 scale-tree 的一个未完成定义。要正确定义 scale-tree，我们需要哪些基本情况？

(define (scale-tree tree factor)
  (cond ;;你的答案写在这里。
        (else 
          (cons (scale-tree (car tree) factor) 
                (scale-tree (cdr tree) factor)))))

选项：

• A. ((null? tree) 0)：对空树返回 0，会在某些情况下给序列末尾拼上多余的 0。你能举出会发生这种情况的例子吗？
• B. ((null? tree) null)：这是一个正确的基本情况，但还需要另一个才能让 scale-tree 正确工作。
• C. ((not (pair? tree)) (* factor tree))：这是一个正确的基本情况，但还需要另一个才能让 scale-tree 正确工作。
• D. A 和 C 都要：单个元素的情况处理正确了，但没有处理空树的情况。
• E. B 和 C 都要：正确！（✅）B 处理参数为空树的情况，C 检查输入的树是否为原子，并正确地将其乘以 factor。

现在，试着在解释器中用一些你自己的例子测试 scale-tree！

示例：deep-reverse

我们来处理一个结构类似的问题。这一次，我们要写一个名为 deep-reverse 的函数，反转深列表中所有元素的顺序。例如：

> (define x (list (list 1 2) (list 3 4)))
((1 2) (3 4))

> (deep-reverse x)
((4 3) (2 1))

注意，不仅 (1 2) 和 (3 4) 交换了位置，它们内部的元素也反了过来。deep-reverse 对内部不含其他列表的列表也应该有效。

测试理解

下面是 deep-reverse 的一个未完成定义。要正确定义 deep-reverse，我们需要哪些递归调用？

(define (deep-reverse d-l)
  (cond ((null? d-l) null)
        ;;你的答案写在这里。
  ))

选项：

• A. ((pair? (car d-l)) (append (deep-reverse (cdr d-l)) (list (deep-reverse (car d-l)))))：这是一个正确的递归调用，但我们还需要另一个才能让 deep-reverse 正确工作。
• B. ((pair? (car d-l)) (append (cdr d-l) (list (deep-reverse (car d-l)))))：d-l 的 cdr 也必须被反转！
• C. (else (append (deep-reverse (cdr d-l)) (list (car d-l))))：这是一个正确的递归调用，但我们还需要另一个才能让 deep-reverse 正确工作。
• D. (else (append (car d-l) (list (deep-reverse (cdr d-l)))))：这个递归调用没有反转 d-l 的 car 和 cdr。
• E. A 和 C 都要：正确！（✅）(car d-l) 是序对的情况由 A 处理，(car d-l) 不是序对的情况由 C 处理。
• F. B 和 D 都要：请分别查看 B 和 D 的解析。

试着在 Racket 解释器中试试看！

要点总结

树可以包含子树，因此在解决涉及树的问题时，递归会非常有用。