LISP - 中序遍历

Common Lisp 中的树遍历

树是计算机科学中的一种基本数据结构。在 Lisp 中，它们可以用多种方式表示。本教程探讨了二叉树经典的**中序遍历 (in-order traversal)**算法，演示了传统的基于列表的方法和更健壮、现代的基于 struct 的实现。

理解中序遍历

中序遍历是一种深度优先算法，它以特定顺序访问二叉树的节点。该算法递归定义如下：

1. 遍历左子树。
1. 访问根节点。
1. 遍历右子树。

对于二叉搜索树，中序遍历会按升序访问节点。考虑以下树：

      A
     / \
    B   C
   / \ / \
D  E F  G

这棵树的中序遍历将产生序列：D, B, E, A, F, C, G。

方法 1：经典的基于列表的表示

在 Lisp 中表示树的一种传统方式是使用嵌套列表，其中每个列表或子列表代表一个节点及其子节点：(node-value left-subtree right-subtree)。

;; 表示为列表的列表的树。
(defvar *my-list-tree* '(A (B (D nil nil) (E nil nil)) (C (F nil nil) (G nil nil))))

在这种结构中，我们使用 car（或 first）等访问器函数来获取值，cadr（或 second）用于左子树，caddr（或 third）用于右子树。

代码：`inorder-list-traversal`

(defun inorder-list-traversal (tree)
  "对基于列表的树执行中序遍历，并打印节点值。"
  (when tree
    (inorder-list-traversal (second tree)) ; 遍历左子树
    (print (first tree))                    ; 访问根节点
    (inorder-list-traversal (third tree))))  ; 遍历右子树

;; --- 用法 ---
(inorder-list-traversal *my-list-tree*)

输出

D
B
E
A
F
C
G

方法 2（最佳实践）：使用 `defstruct`

虽然基于列表的树很简单，但它们不够健壮。一种现代、推荐的方法是使用 defstruct（或 defclass）来为节点定义一个清晰的结构。这使得代码更具可读性、类型安全性和可维护性。

(defstruct node
  value
  left
  right)

defstruct 会自动创建构造函数 make-node 以及访问器 node-value、node-left 和 node-right。

代码：构建和遍历基于结构体的树

;; --- 定义一个可测试的遍历函数，返回一个列表 ---
(defun inorder-traversal (tree)
  "对基于结构体的树执行中序遍历，返回一个值列表。"
  (when tree
    (append (inorder-traversal (node-left tree))
            (list (node-value tree))
            (inorder-traversal (node-right tree)))))

;; --- 使用我们的结构体创建树 ---
(defvar *my-struct-tree*
  (make-node :value 'A
             :left (make-node :value 'B
                            :left (make-node :value 'D)
                            :right (make-node :value 'E'))
             :right (make-node :value 'C
                             :left (make-node :value 'F)
                             :right (make-node :value 'G'))))

;; --- 用法和测试 ---
(let ((result (inorder-traversal *my-struct-tree*)))
  (print result)
  ;; 最佳实践：添加一个测试以验证结果
  (assert (equal result '(D B E A F C G))))

输出

(D B E A F C G)

进一步探索：前序遍历和后序遍历

通过重新排列这三个基本步骤，您可以实现其他标准遍历：

前序遍历 (Pre-order Traversal)（根、左、右）：适用于创建树的副本。序列：A, B, D, E, C, F, G。
后序遍历 (Post-order Traversal)（左、右、根）：适用于删除树，因为您在删除父节点之前删除子节点。序列：D, E, B, F, G, C, A。