Skip to content

LISP - 修改树

Lisp - 修改树结构

在本章中，我们将在理解树的基础上，重点关注如何修改树：搜索节点、添加新节点和删除现有节点。我们将使用通用树，其中一个节点可以有任意数量的子节点。我们的方法将是函数式的，这意味着我们的修改函数将返回一个新的、更新后的树，而不是就地改变原始树。

通用树的表示

我们将把通用树的节点表示为一个列表，其中第一个元素是节点的值，列表的其余部分包含其子节点（子树）。

;; 示例树：A 是根节点，子节点为 B 和 C。
;; B 有子节点 D 和 E。C 有一个子节点 F。
(defvar *my-general-tree* '(A (B (D) (E)) (C (F))))

;; --- 抽象辅助函数 ---
(defun node-value (tree)
  "获取树根节点的值。"
  (first tree))

(defun node-children (tree)
  "获取根节点的子节点列表。"
  (rest tree))

1. 搜索节点

要搜索一个节点，我们检查当前节点的值。如果不匹配，我们就在其每个子节点中递归搜索。some 函数在这里非常适用，因为它一旦任何递归调用找到匹配项，就会停止并返回 T。

(defun search-node (tree node-to-find)
  "在树中搜索节点。如果找到则返回 T，否则返回 NIL。"
  (when tree
    (if (eql (node-value tree) node-to-find)
        t ; Found it at the current node
        (some #'(lambda (subtree) (search-node subtree node-to-find))
              (node-children tree)))))

2. 添加节点

我们的 insert-node 函数会将一个新的子节点添加到指定的父节点。它会返回一个经过修改的新树。如果未找到父节点，则返回原始树。

(defun insert-node (tree parent-value new-child-node)
  "非破坏性地向父节点插入一个新子节点。"
  (if (null tree)
      nil
      (if (eql (node-value tree) parent-value)
          ;; 找到父节点，构造一个添加了新子节点的新节点。
          (cons (node-value tree) (cons new-child-node (node-children tree)))
          ;; 否则，在子节点上递归并重建树。
          (cons (node-value tree)
                (mapcar #'(lambda (subtree)
                            (insert-node subtree parent-value new-child-node))
                        (node-children tree))))))

3. 删除节点

删除节点更为复杂。我们的函数将构建一个新树，该新树排除指定节点及其整个子树。原始教程的实现存在缺陷，因为它留下了 NIL 占位符。一个正确的函数式方法会重建父节点的子列表，但不包含已删除的节点。

(defun delete-node (tree node-to-delete)
  "非破坏性地删除节点及其子树。"
  (if (null tree)
      nil
      (let* ((current-value (node-value tree))
             (children (node-children tree))
             ;; 步骤 1：递归处理子节点以处理树中更深层的删除。
             (processed-children
               (mapcar #'(lambda (child) (delete-node child node-to-delete)) children))
             ;; 步骤 2：过滤掉任何变为待删除节点的子节点。
             (filtered-children
               (remove-if #'(lambda (child) (eql (node-value child) node-to-delete))
                          processed-children)))
        ;; 步骤 3：如果当前节点是要删除的节点，则返回 nil，否则重构它。
        (if (eql current-value node-to-delete)
            nil
            (cons current-value filtered-children)))))

完整示例（`main.lisp`）

;; 定义树和辅助函数（如上所示）
(defvar *my-general-tree* '(A (B (D) (E)) (C (F))))

;; --- 初始状态 ---
(format t "Original Tree: ~s~%" *my-general-tree*)

;; --- 搜索 ---
(format t "Searching for 'D': ~a~%" (search-node *my-general-tree* 'D)) ; ==> T
(format t "Searching for 'Z': ~a~%~%" (search-node *my-general-tree* 'Z)) ; ==> NIL

;; --- 插入 ---
(format t "Inserting '(G)' under 'B'...~%")
(setf *my-general-tree* (insert-node *my-general-tree* 'B '(G)))
(format t "Tree after insert: ~s~%~%" *my-general-tree*)

;; --- 删除 ---
(format t "Deleting node 'D'...~%")
(setf *my-general-tree* (delete-node *my-general-tree* 'D))
(format t "Tree after delete: ~s~%" *my-general-tree*)

输出

Original Tree: (A (B (D) (E)) (C (F)))
Searching for 'D': T
Searching for 'Z': NIL

Inserting '(G)' under 'B'...
Tree after insert: (A (B (G) (D) (E)) (C (F)))

Deleting node 'D'...
Tree after delete: (A (B (G) (E)) (C (F)))

最佳实践与进一步学习

函数纯粹性：请注意我们的函数如何不修改输入树。它们返回一个新树。这可以防止副作用，并使代码更容易理解，尤其是在复杂或并发程序中。
边缘情况：我们的函数优雅地处理 null 树。一个健壮的实现还会考虑插入操作的父节点不存在时该怎么做。
性能：对于非常大且频繁修改的树，这种函数式方法可能由于大量的列表复制而效率低下。在这种情况下，开发人员可能会谨慎使用破坏性操作或选择完全不同的数据结构（如哈希表或 CLOS 对象）。
项目构想：尝试建模一个简单的文件系统。实现 find-path、mkdir（插入）和 rm（删除）等函数。