LISP - 后序遍历

Lisp - 后序树遍历（Post-order Tree Traversal）

树遍历（Tree traversal）是计算机科学中的一个基本算法。本章演示了如何在 Common Lisp 中对表示为二叉树的结构执行后序遍历（post-order traversal）。

后序遍历（Post-order Traversal）解释

在后序遍历中，我们按照特定的顺序处理二叉树的节点：

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

这种“左-右-根”模式递归地应用于树中的每个节点。

考虑以下二叉树：

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

后序遍历将按此顺序访问节点：

D → E → B → F → G → C → A

这种遍历顺序在计算文件系统目录大小或删除树中节点等场景中非常有用，因为你会在处理父节点之前处理子节点。

Lisp 中的树表示

在 Lisp 中表示树有多种方法。一种经典、简单的方法是使用嵌套列表，但更健壮和现代的方法是使用 defstruct。

现代方法：使用 defstruct

使用 defstruct 为我们的树节点创建了一个专用数据结构。这使得代码比使用普通列表更清晰、不易出错且更高效。

;; 定义一个二叉树节点结构体
(defstruct node
  value  ; 该节点的数据
  left   ; 左子节点（另一个节点或 nil）
  right) ; 右子节点（另一个节点或 nil）

;; 使用节点结构体构造示例树
(defvar *my-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))))

(print *my-tree*)

在这里，make-node 创建了我们 node 结构体的一个实例，并且像 node-value、node-left 和 node-right 这样的访问器（accessors）是自动为我们创建的。

示例：后序遍历实现

该实现是递归算法的直接翻译。

main.lisp

;; 定义一个二叉树节点结构体
(defstruct node
  value
  left
  right)

;; 遍历函数
(defun post-order-traversal (tree-node)
  ;; 仅当当前节点不为 nil 时才继续
  (when tree-node
    ;; 1. 遍历左子树
    (post-order-traversal (node-left tree-node))

    ;; 2. 遍历右子树
    (post-order-traversal (node-right tree-node))

    ;; 3. 访问根节点（此处为打印其值）
    (format t "~a " (node-value tree-node))))

;; 构造示例树
(defvar *my-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))))

;; 执行遍历并在末尾打印换行符
(post-order-traversal *my-tree*)
(terpri)

输出

当你加载并运行这段代码时，它将生成预期的后序序列：

D E B F G C A

解释

• defun：定义函数 post-order-traversal。
• when tree-node：这是递归的基本情况（base case）。如果函数在空子节点 (nil) 上被调用，它什么也不做并返回。
• node-left 和 node-right：这些是 defstruct 自动生成的访问器函数（accessor functions）。它们用于检索节点的左子节点和右子节点。
• node-value：此访问器检索存储在当前节点的数据。
• 递归（Recursion）：函数在左子节点和右子节点上调用自身。此过程一直持续到到达树的叶子节点（子节点为 nil 的节点），此时它开始随着递归的展开打印值。

测试遍历

为了正确测试此类函数，你可以修改它，使其返回一个值列表而不是打印它们。这允许进行自动化验证。

(defun post-order-collect (tree-node)
  (when tree-node
    (append (post-order-collect (node-left tree-node))
            (post-order-collect (node-right tree-node))
            (list (node-value tree-node)))))

;; 测试断言
(assert (equal (post-order-collect *my-tree*)
               '(D E B F G C A)))

(format t "Test passed!~%")