LISP - 树

Lisp - 树的运用

在 Lisp 中，基本数据结构——列表 (list)，本身就是一棵树。列表由 cons 单元格构建而成，每个单元格都有一个 car（值）和一个 cdr（指向下一个单元格的指针）。这种递归结构使得 Lisp 非常适合创建和操作树状数据结构。

使用列表表示树

在 Lisp 中表示通用（N叉）树的常见惯用方式是使用嵌套列表。一个节点被表示为一个列表，其中第一个元素是节点的数据，其余元素是它的子节点（它们本身也是树）。

考虑以下这棵树：

在 Lisp 中，这可以优雅地表示为：

(A (B) (C (E)) (D (F (G) (H))))

这里，A 是根节点，有三个子节点：B、C 和 D。B 是一个叶节点（没有子节点）。C 有一个子节点 E。D 有一个子节点 F，而 F 又有两个子节点 G 和 H。

内置树相关函数

Common Lisp 提供了几个对于处理树状列表结构特别有用的函数。

函数	描述
copy-tree tree	递归复制整个由 `cons` 单元格组成的树。与只复制顶层的 `copy-list` 不同，`copy-tree` 创建一个全新的结构。
tree-equal x y &key :test	递归比较两棵树是否相等。它检查结构是否相同，以及对应元素是否相等（默认为 `eql`）。
subst new old tree &key :test	将 `tree` 中 `old` 的所有出现替换为 `new`。这是一个非破坏性函数；它返回一棵新树。
nsubst new old tree &key :test	`subst` 的破坏性版本。它原地修改原始树，这可以提高内存效率，但应谨慎使用。
sublis alist tree &key :test	根据关联列表（`alist`）一次性执行多重替换。树中的每个项都会在 `alist` 中查找，如果找到，则替换为其关联值。
nsublis alist tree &key :test	`sublis` 的破坏性版本。

示例：使用 `subst` 和 `copy-tree`

本示例演示了如何创建一棵树，对其进行深拷贝，然后在新的副本中替换一个值，而原始树保持不变。

;;; main.lisp

(let* ((original-tree '(A (B) (C (B))))
       (copied-tree (copy-tree original-tree))
       (modified-tree (subst 'X 'B copied-tree)))

  (format t "Original Tree: ~s~%" original-tree)
  (format t "Copied Tree:   ~s~%" copied-tree) ; 在 nsubst 之前仍未改变
  (format t "Modified Tree: ~s~%" modified-tree)

  (format t "~%--- Verifying non-destruction ---")
  (format t "~%Is the original tree still the same? ~a~%"
          (tree-equal original-tree '(A (B) (C (B))))))

;; 现在我们展示破坏性版本
(nsubst 'Z 'A copied-tree)
(format t "~%--- 破坏性 nsubst 之后 ---")
(format t "~%The 'copied-tree' is now modified: ~s~%" copied-tree)

输出

Original Tree: (A (B) (C (B)))
Copied Tree:   (A (B) (C (B)))
Modified Tree: (A (X) (C (X)))

--- Verifying non-destruction ---
Is the original tree still the same? T

--- After destructive nsubst ---
The 'copied-tree' is now modified: (Z (B) (C (B)))

构建自己的树工具

虽然 Lisp 的内置函数功能强大，但您通常会为常见的树操作（如遍历或搜索）定义自己的辅助函数。让我们为基于列表的树表示创建一个小型实用程序集。

节点访问器

这些简单的函数提供了一个清晰的 API 来访问节点的各个部分。

(defun node-data (node)
  "返回树节点的数据。"
  (first node))

(defun node-children (node)
  "返回树节点的子节点列表。"
  (rest node))

树遍历

经典的树操作是遍历。这是一个对树进行前序遍历的函数，它将每个节点的数据收集到一个扁平列表中。

(defun pre-order-traversal (tree)
  "对树进行前序遍历，返回节点数据的列表。"
  (when tree
    (cons (node-data tree)
          (loop for child in (node-children tree)
                append (pre-order-traversal child)))))

示例：构建和遍历树

让我们使用我们的辅助函数来构建然后遍历一个示例树。

;;; main.lisp

;; 上述辅助函数
(defun node-data (node) (first node))
(defun node-children (node) (rest node))

(defun pre-order-traversal (tree)
  (when tree
    (cons (node-data tree)
          (loop for child in (node-children tree)
                append (pre-order-traversal child)))))

;; 定义我们的文件系统树
(let ((fs-tree '(("/")
                 (("home")
                  (("alice")
                   ("notes.txt")
                   ("work.lisp")))
                 (("etc")
                  ("passwd")
                  ("hosts")))))

  (format t "File System Tree:~%~s~%~%" fs-tree)
  (format t "Data of root node: ~s~%" (node-data fs-tree))
  (format t "Children of root node: ~s~%~%" (node-children fs-tree))

  (let ((traversal-result (pre-order-traversal fs-tree)))
    (format t "Pre-order traversal of all nodes:~%~s~%" traversal-result)))

输出

File System Tree:
(("/" (("home" (("alice" "notes.txt" "work.lisp")))) (("etc" "passwd" "hosts"))))

Data of root node: ("/")
Children of root node: ((("home" (("alice" "notes.txt" "work.lisp")))) (("etc" "passwd" "hosts")))

Pre-order traversal of all nodes:
(("/" (("home" (("alice" "notes.txt" "work.lisp")))) (("etc" "passwd" "hosts"))) ("home" (("alice" "notes.txt" "work.lisp"))) ("alice" "notes.txt" "work.lisp") "notes.txt" "work.lisp" ("etc" "passwd" "hosts") "passwd" "hosts")

实际应用：迷你项目

树的一个很好的用途是表示分层数据，例如文件系统、游戏中的场景图或 HTML 文档。一个有用的函数将是在这棵树中搜索特定节点。

(defun find-node (data tree &key (test #'equal))
  "递归搜索树中具有给定数据的节点。"
  (cond
    ;; 如果树为空，则未找到。
    ((null tree) nil)
    ;; 如果当前节点的数据匹配，则找到了。
    ((funcall test data (node-data tree)) tree)
    ;; 否则，在子节点中搜索。
    (t (loop for child in (node-children tree)
             thereis (find-node data child :test test)))))

;; --- 示例用法 ---
(let ((my-tree '(A (B (C)) (D))))
  (format t "~&Searching for node 'C' in ~s...~%" my-tree)
  (let ((found (find-node 'C my-tree)))
    (format t "Found subtree: ~s~%" found)))

输出

Searching for node 'C' in (A (B (C)) (D))...
Found subtree: (C)