LISP - 搜索树

Lisp - 树形结构搜索

树是一种基本的数据结构，在 Lisp 中，它们自然地使用列表表示。本教程涵盖了在树形结构中搜索值的现代、惯用方法。

使用列表表示树

在 Lisp 中表示树的一种常见且简单的方法是使用嵌套列表。我们将考虑两种形式：

• 二叉树：每个节点都是形如 (value left-subtree right-subtree) 的列表。空子树用 NIL 表示。
• 通用树：每个节点都是形如 (value child1 child2 ... childN) 的列表。

示例定义

;; 一个二叉树：(1 (2 nil (3 nil nil)) (4 (5 nil nil) nil))
(defparameter *binary-tree*
  '(1 (2 nil (3 nil nil))
      (4 (5 nil nil) nil)))

;; 一个通用树：(A (B (C) (D)) (E (F) (G)))
(defparameter *generic-tree*
  '(A (B (C) (D))
      (E (F) (G))))

;; 注意：使用 `*earmuffs*` 是一种命名全局特殊变量的约定。

现代函数式搜索算法

我们可以编写一个单一、优雅的深度优先搜索（DFS）函数，它适用于两种树表示。与手动循环相比，使用 some 的函数式方法更简洁和惯用。

main.lisp

(defun tree-contains-p (target tree)
  "使用 DFS 在基于列表的通用 TREE 中搜索 TARGET。如果找到则返回 T，否则返回 NIL。"
  (when tree
    (let ((node-value (first tree))
          (children (rest tree)))
      (or (eql node-value target)
          (some (lambda (child) (tree-contains-p target child))
                children)))))

;; --- 搜索二叉树 ---
(format t "Binary tree contains 3: ~a~%" (tree-contains-p 3 *binary-tree*))
(format t "Binary tree contains 6: ~a~%" (tree-contains-p 6 *binary-tree*))

;; --- 搜索通用树 ---
(format t "Generic tree contains 'G: ~a~%" (tree-contains-p 'G *generic-tree*))
(format t "Generic tree contains 'Z: ~a~%" (tree-contains-p 'Z *generic-tree*))

输出

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

Binary tree contains 3: T
Binary tree contains 6: NIL
Generic tree contains 'G: T
Generic tree contains 'Z: NIL

tree-contains-p 函数解释

• (when tree ...)：递归的基准情况。如果树（或子树）是 NIL，表示它为空，我们就停止并返回 NIL。
• (let ...)：我们将节点的值 (first tree) 及其子节点 (rest tree) 局部绑定到变量。这提高了可读性。
• (or ...)：这是逻辑的核心。它首先检查当前 node-value 是否是 target。
• (some ...)：如果当前节点未找到目标，some 会递归地将搜索函数应用于每个子节点。一旦任何递归调用找到目标，some 就会方便地停止并返回一个真值，从而使搜索高效。

超越列表：使用 defstruct 的更健壮方法

虽然基于列表的树非常适合学习，但实际应用通常受益于使用 defstruct 或 defclass 更结构化和健壮的表示。defstruct 会自动为你的节点创建构造函数、访问器和类型。

使用 defstruct 的示例

;; 定义二叉树节点的结构
(defstruct bnode
  value
  left
  right)

;; 使用结构创建树
(let ((struct-tree (make-bnode :value 'A
                               :left (make-bnode :value 'B')
                               :right (make-bnode :value 'C'))))

  ;; 使用自动生成的函数访问数据
  (format t "Root value of struct tree: ~a~%" (bnode-value struct-tree))
  (format t "Left child's value: ~a~%" (bnode-value (bnode-left struct-tree))))

;; 为这个结构重写搜索函数会更健壮，通常也更快。