LISP - 递归遍历

Lisp - 递归树遍历

Lisp 的优雅之处在于其递归数据处理能力，树遍历就是一个经典示例。树是由节点组成的分层数据结构。在本更新的教程中，我们将探索在 Common Lisp 中表示和遍历二叉树的现代、健壮方法，重点关注数据抽象等最佳实践。

二叉树的现代表示

二叉树是一种每个节点最多有两个子节点（称为左子节点和右子节点）的树。虽然我们可以使用原始列表，但更好的做法是定义清晰的结构并使用访问器函数与其交互。这会将结构的实现与其使用分离。

我们将把一个节点表示为一个三元素列表：(value left-subtree right-subtree)。空树或缺失的子节点将由 NIL 表示。

; 让我们定义树结构：
(defvar *my-tree* '(A (B (D NIL NIL) (E NIL NIL)) (C (F NIL NIL) (G NIL NIL))))

; 抽象结构的辅助函数
(defun node-value (node)
  "返回节点的值。"
  (first node))

(defun left-child (node)
  "返回左子树。"
  (second node))

(defun right-child (node)
  "返回右子树。"
  (third node))

使用这些辅助函数使我们的代码更简洁，并且当我们决定改变底层树表示（例如，从列表到 struct 或 class）时，也更不容易出错。

实现树遍历算法

有三种主要的递归遍历二叉树的方法。我们将实现这三种：前序、中序和后序。

1. 前序遍历（根、左、右）

在前序遍历中，我们首先处理当前节点的值，然后递归遍历左子树，最后遍历右子树。

(defun pre-order-traverse (tree)
  "对树进行前序遍历，打印节点值。"
  (when tree
    (print (node-value tree))
    (pre-order-traverse (left-child tree))
    (pre-order-traverse (right-child tree))))

2. 中序遍历（左、根、右）

中序遍历首先递归遍历左子树，然后处理当前节点的值，最后遍历右子树。对于二叉搜索树，这将按升序访问节点。

(defun in-order-traverse (tree)
  "对树进行中序遍历，打印节点值。"
  (when tree
    (in-order-traverse (left-child tree))
    (print (node-value tree))
    (in-order-traverse (right-child tree))))

3. 后序遍历（左、右、根）

在后序遍历中，我们首先递归遍历左子树和右子树，最后处理当前节点的值。这对于从树中删除节点等任务很有用。

(defun post-order-traverse (tree)
  "对树进行后序遍历，打印节点值。"
  (when tree
    (post-order-traverse (left-child tree))
    (post-order-traverse (right-child tree))
    (print (node-value tree))))

完整示例（main.lisp）

;;; Common Lisp 中的现代二叉树遍历

;; --- 数据定义 ---
(defvar *my-tree* '(A (B (D NIL NIL) (E NIL NIL)) (C (F NIL NIL) (G NIL NIL))))

;; --- 数据抽象（辅助函数） ---
(defun node-value (node) "返回节点的值。" (first node))
(defun left-child (node) "返回左子树。" (second node))
(defun right-child (node) "返回右子树。" (third node))

;; --- 遍历算法 ---
(defun pre-order-traverse (tree)
  (when tree
    (format t "~a " (node-value tree))
    (pre-order-traverse (left-child tree))
    (pre-order-traverse (right-child tree))))

(defun in-order-traverse (tree)
  (when tree
    (in-order-traverse (left-child tree))
    (format t "~a " (node-value tree))
    (in-order-traverse (right-child tree))))

(defun post-order-traverse (tree)
  (when tree
    (post-order-traverse (left-child tree))
    (post-order-traverse (right-child tree))
    (format t "~a " (node-value tree))))

;; --- 执行 ---
(format t "Original Tree:~%~s~%~%" *my-tree*)

(format t "Pre-order Traversal: ")
(pre-order-traverse *my-tree*)
(terpri)

(format t "In-order Traversal:  ")
(in-order-traverse *my-tree*)
(terpri)

(format t "Post-order Traversal: ")
(post-order-traverse *my-tree*)
(terpri)

输出

执行代码后，将返回以下结果：

Original Tree:
(A (B (D NIL NIL) (E NIL NIL)) (C (F NIL NIL) (G NIL NIL)))

Pre-order Traversal: A B D E C F G
In-order Traversal:  D B E A F C G
Post-order Traversal: D E B F G C A

关键概念与最佳实践

• 数据抽象：使用 node-value 和 left-child 等函数将你的逻辑与特定列表结构解耦。这是优秀软件工程的核心原则。
• 递归基例：(when tree ...) 形式（等同于 (if tree ...)）提供了递归必不可少的基例。当节点为 NIL 时，函数不做任何操作并返回，从而停止递归调用。
• destructuring-bind 的清晰性：为了使代码更简洁，你可以在函数内部使用 destructuring-bind：

  (destructuring-bind (value left right) tree
    ; ... 直接使用 value、left、right
  )

• 进阶步骤：对于更复杂的应用程序，考虑使用 DEFSTRUCT 或 Common Lisp 对象系统 (DEFCLASS) 来定义你的节点。这提供了类型安全和更正式的结构。