3.8 树 (Trees)

Cons 对象可以想成是二叉树， car 代表左子树，而 cdr 代表右子树。举例来说，列表

(a (b c) d) 也是一棵由图 3.8 所代表的树。 （如果你逆时针旋转 45 度，你会发现跟图 3.3 一模一样）

../_images/Figure-3.8.png

图 3.8 二叉树 (Binary Tree)

Common Lisp 有几个内置的操作树的函数。举例来说， copy-tree 接受一个树，并返回一份副本。它可以这么定义：

  1. (defun our-copy-tree (tr)
  2.   (if (atom tr)
  3.        tr
  4.        (cons (our-copy-tree (car tr))
  5.              (our-copy-tree (cdr tr)))))

把这跟 36 页的 copy-list 比较一下； copy-tree 复制每一个 Cons 对象的 car 与 cdr ，而 copy-list 仅复制 cdr 。

没有内部节点的二叉树没有太大的用处。 Common Lisp 包含了操作树的函数，不只是因为我们需要树这个结构，而是因为我们需要一种方法，来操作列表及所有内部的列表。举例来说，假设我们有一个这样的列表：

  1. (and (integerp x) (zerop (mod x 2)))

而我们想要把各处的 x 都换成 y 。调用 substitute 是不行的，它只能替换序列 (sequence)中的元素：

  1. > (substitute 'y 'x '(and (integerp x) (zerop (mod x 2))))
  2. (AND (INTEGERP X) (ZEROP (MOD X 2)))

这个调用是无效的，因为列表有三个元素，没有一个元素是 x 。我们在这所需要的是 subst ，它替换树之中的元素。

  1. > (subst 'y 'x '(and (integerp x) (zerop (mod x 2))))
  2. (AND (INTEGERP Y) (ZEROP (MOD Y 2)))

如果我们定义一个 subst 的版本，它看起来跟 copy-tree 很相似：

  1. > (defun our-subst (new old tree)
  2.     (if (eql tree old)
  3.         new
  4.         (if (atom tree)
  5.             tree
  6.             (cons (our-subst new old (car tree))
  7.                   (our-subst new old (cdr tree))))))

操作树的函数通常有这种形式， car 与 cdr 同时做递归。这种函数被称之为是 双重递归 (doubly recursive)。