LISP - 深度优先遍历

Lisp - 树遍历：深度优先搜索

树是一种基本的分层数据结构。深度优先搜索 (DFS) 是一种经典的树遍历或搜索算法。它在回溯之前会尽可能深地探索每条分支。在本教程中，我们将在 Common Lisp 中实现二叉树的三种主要 DFS 遍历类型。

表示二叉树

在 Lisp 中表示二叉树的一种常见方法是使用嵌套列表 (nested lists)。我们将使用 (VALUE LEFT-SUBTREE RIGHT-SUBTREE) 格式，其中 NIL 表示空子树。

让我们定义一个将用于示例的样本树：

;;      F
;;     / \
;;    B   G
;;   / \   \
;;  A   D   I
;;     / \   /
;;    C   E H

(defvar *my-tree*
  '(F (B (A nil nil)
         (D (C nil nil)
            (E nil nil)))
     (G nil
        (I (H nil nil)
           nil))))

为了让代码更简洁，我们来定义一些辅助函数 (helper functions) 来访问节点的部分。

(defun node-value (node) (first node))
(defun left-child (node) (second node))
(defun right-child (node) (third node))

1. 前序遍历 (根、左、右)

在前序遍历中，我们首先访问当前节点 (node)，然后递归遍历左子树 (left subtree)，最后递归遍历右子树 (right subtree)。

实现

(defun pre-order-traversal (tree)
  (when tree
    (cons (node-value tree)
          (append (pre-order-traversal (left-child tree))
                  (pre-order-traversal (right-child tree))))))

;; 在我们的树上运行遍历
(print (pre-order-traversal *my-tree*))

输出

(F B A D C E G I H)

2. 中序遍历 (左、根、右)

在中序遍历中，我们首先递归遍历左子树，然后访问当前节点，最后递归遍历右子树。对于二叉搜索树 (binary search tree) 而言，这种遍历会按排序顺序访问节点。

实现

(defun in-order-traversal (tree)
  (when tree
    (append (in-order-traversal (left-child tree))
            (list (node-value tree))
            (in-order-traversal (right-child tree)))))

;; 在我们的树上运行遍历
(print (in-order-traversal *my-tree*))

输出

(A B C D E F G H I)

3. 后序遍历 (左、右、根)

在后序遍历中，我们首先递归遍历左子树和右子树，最后才访问当前节点。这对于在处理节点之前必须先处理其子节点的各种操作很有用，例如释放节点的内存。

实现

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

;; 在我们的树上运行遍历
(print (post-order-traversal *my-tree*))

输出

(A C E D B H I G F)

实际应用

深度优先搜索算法是计算机科学的基础，并应用于：

• 拓扑排序 (Topological Sorting)：对有依赖关系的任务进行排序。
• 寻路 (Pathfinding)：在图中寻找两节点之间的路径，例如在迷宫中寻路。
• 编译器 (Compilers)：构建和处理抽象语法树 (abstract syntax trees)。
• 人工智能 (AI)：在游戏和规划问题中搜索状态空间。