LISP - 二叉树

Lisp - 实现二叉搜索树

二叉搜索树（Binary Search Tree，简称 BST）是一种基本数据结构，它支持快速的数据查找、插入和删除。它是一种基于节点的二叉树，具有以下特性：

节点左子节点（及其所有后代）中的值小于或等于节点自身的值。
节点右子节点（及其所有后代）中的值大于节点自身的值。
左右子树也必须是二叉搜索树。

这种结构允许高效搜索，因为每一步你都可以消除剩余树的一半，从而实现平均时间复杂度为 O(log n)。

使用 `defstruct` 进行现代表示

尽管可以使用嵌套列表来表示树，但更健壮、更符合 Common Lisp 习惯的方法是使用 defstruct。这会为我们的节点创建一个专门的数据类型，包含构造函数和访问器，从而使代码更具可读性和可维护性。

;; 定义 BST 中单个节点的结构。
(defstruct bst-node
  (value nil :type number) ; 节点的数据
  (left  nil :type (or null bst-node)) ; 指向左子节点的指针
  (right nil :type (or null bst-node)) ; 指向右子节点的指针
  )

;; `defstruct` 自动为我们提供了：
;; - 构造函数：(make-bst-node :value ...)
;; - 访问器：(bst-node-value ...), (bst-node-left ...), 等。
;; - 复制器：(copy-bst-node ...)

核心操作

插入值

我们的 insert 函数将是递归的。它根据 BST 规则找到新值的正确位置，并在那里插入一个新节点。它返回树的（可能是新的）根。

(defun bst-insert (tree value)
  "将值插入 BST 并返回新的树根。"
  (if (null tree)
      (make-bst-node :value value)
      (let ((node-value (bst-node-value tree)))
        (cond
          ((<= value node-value)
           (setf (bst-node-left tree) (bst-insert (bst-node-left tree) value)))
          ((> value node-value)
           (setf (bst-node-right tree) (bst-insert (bst-node-right tree) value))))
        tree)))

查找值

搜索遵循相同的逻辑：在每个节点，我们决定是向左、向右，还是已经找到了我们的值。

(defun bst-search (tree value)
  "在 BST 中搜索一个值。如果找到，返回节点；否则返回 NIL。"
  (when tree
    (let ((node-value (bst-node-value tree)))
      (cond
        ((= value node-value) tree)
        ((< value node-value) (bst-search (bst-node-left tree) value))
        ((> value node-value) (bst-search (bst-node-right tree) value))))))

遍历树

树遍历是按照特定顺序访问每个节点的过程。最常见的三种遍历是中序（In-order）、前序（Pre-order）和后序（Post-order）。

main.lisp

;; 中序遍历函数（左、节点、右）
;; 对于 BST，这将按排序顺序打印值。
(defun bst-in-order (tree)
  (when tree
    (bst-in-order (bst-node-left tree))
    (format t "~a " (bst-node-value tree))
    (bst-in-order (bst-node-right tree))))

;; 前序遍历函数（节点、左、右）
(defun bst-pre-order (tree)
  (when tree
    (format t "~a " (bst-node-value tree))
    (bst-pre-order (bst-node-left tree))
    (bst-pre-order (bst-node-right tree))))

;; --- 综合示例 ---

;; 1. 创建一个空树
(defvar *my-tree* nil)

;; 2. 插入元素。我们使用一个辅助函数从列表中构建。
(dolist (val '(27 14 35 10 19 31 42))
  (setf *my-tree* (bst-insert *my-tree* val)))

;; 3. 执行遍历
(format t "In-order (sorted): ")
(bst-in-order *my-tree*)
(terpri)

(format t "Pre-order: ")
(bst-pre-order *my-tree*)
(terpri)

;; 4. 搜索一个值
(format t "Searching for 19: ~a~%" (if (bst-search *my-tree* 19) "Found" "Not Found"))
(format t "Searching for 99: ~a~%" (if (bst-search *my-tree* 99) "Found" "Not Found"))

Output

In-order (sorted): 10 14 19 27 31 35 42
Pre-order: 27 14 10 19 35 31 42
Searching for 19: Found
Searching for 99: Not Found

深入学习

这个实现是一个很好的开始。然而，在实际应用中，你需要考虑一个关键问题：树的平衡。如果你插入的是排序好的数据（例如 1, 2, 3, 4, 5），这个简单的 BST 将退化成一个链表，其性能将下降到 O(n)。

对于生产环境使用，你应该研究自平衡二叉搜索树，例如 AVL 树或红黑树，它们在插入和删除时会执行小幅旋转以保持树的平衡，并保证 O(log n) 的性能。