LISP - 前序遍历

Lisp - 树的前序遍历

树遍历是访问树中每个节点且仅访问一次的过程。在 Lisp 中，树通常表示为列表，我们可以优雅地使用递归实现遍历算法。本教程重点介绍前序遍历。

前序遍历算法

前序遍历遵循特定的顺序：根 -> 左 -> 右。这意味着对于任何给定节点，我们：

访问根节点本身。
递归地对其整个左子树执行前序遍历。
递归地对其整个右子树执行前序遍历。

考虑以下二叉树：

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

前序遍历将按此确切顺序访问节点： A → B → D → E → C → F → G

实现：收集节点

一个好的做法是编写一个遍历函数，它返回一个已访问节点的列表，而不是打印它们。这将遍历逻辑与输出逻辑分离，使函数更具复用性。

我们将使用列表表示 (value left-subtree right-subtree) 作为我们的二叉树。

main.lisp

;; 为了清晰起见，使用全局参数定义树
(defparameter *my-tree*
  '(A (B (D nil nil) (E nil nil))
      (C (F nil nil) (G nil nil))))

(defun collect-preorder (tree)
  "对二叉树 TREE 执行前序遍历。返回按遍历顺序排列的节点值列表。"
  (when tree
    (let ((value (first tree))
          (left (second tree))
          (right (third tree)))
      (cons value ; 1. 根
            (append (collect-preorder left)  ; 2. 左子树
                    (collect-preorder right) ; 3. 右子树
             ))))))

;; --- 执行并打印结果 ---
(let ((traversal-result (collect-preorder *my-tree*)))
  (format t "The tree definition is: ~s~%" *my-tree*)
  (format t "Pre-order traversal result: ~s~%" traversal-result))

输出

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

The tree definition is: (A (B (D NIL NIL) (E NIL NIL)) (C (F NIL NIL) (G NIL NIL)))
Pre-order traversal result: (A B D E C F G)

解释

when tree：这是我们的基准情况。如果子树是 nil，递归停止并返回 nil。
let：我们将节点的部分（value、left、right）赋值给局部变量以增加清晰度。这避免了对 first、second 等函数的重复调用。
cons 和 append：结果通过将当前节点的 value cons 到左子树和右子树遍历结果的 append 列表上构建。这直接反映了根 -> 左 -> 右的逻辑。

性能考量与替代方案

在递归内部使用 append 对于非常深或不平衡的树可能效率低下，因为它会重复创建新列表。一种更高效且惯用的 Lisp 方法是使用带有局部辅助函数的累加器。

(defun collect-preorder-efficient (tree)
  "使用累加器进行更高效的前序遍历。"
  (let ((result nil)) ; 这将以相反的顺序累积节点
    (labels ((traverse (subtree)
               (when subtree
                 (push (first subtree) result)
                 (traverse (third subtree))  ; 先处理右子树...
                 (traverse (second subtree))))) ; ...然后左子树
      (traverse tree))
    (nreverse result))) ; 最后反转列表以获得正确的顺序

;; (collect-preorder-efficient *my-tree*) 也会返回 (A B D E C F G)

在这个版本中，push 是一个非常快速的操作。我们先遍历右子树再遍历左子树，这样当我们 nreverse 最终列表时，左子树的元素就能正确地出现在右子树之前。这种 (push ... (nreverse ...)) 模式是 Lisp 中构建列表的一种常见且高效的惯用写法。