Common Lisp 中二叉搜索树实现中的类型错误

Question

我目前正在 Common Lisp 中实现二叉搜索树，并且遇到了类型错误。当我尝试在树中查找最小或最大键时，会出现错误。这是我的代码的相关部分：

;; Define the node structure for a binary search tree
(defstruct (node (:conc-name nil))
  key     ; The object stored in the node
  (lc nil) ; The left child of the node
  (rc nil) ; The right child of the node
  (parent nil)) ; The parent of the node

;; Function to insert a key into the BST
(defun bst-insert (key tree compare-fn)
  (cond ((null tree) 
         (make-node :key key :lc nil :rc nil)) ; Create a new node if tree is empty
        ((funcall compare-fn key (key tree)) 
         (setf (lc tree) (bst-insert key (lc tree) compare-fn))) ; Insert in left subtree
        (t 
         (setf (rc tree) (bst-insert key (rc tree) compare-fn)))) ; Insert in right subtree
  tree)

;; Function to find a key in the BST
(defun bst-find (key tree compare-fn)
  (cond ((null tree) nil) ; Key not found
        ((funcall compare-fn key (key tree)) (bst-find key (lc tree) compare-fn)) ; Search in left subtree
        ((funcall compare-fn (key tree) key) (bst-find key (rc tree) compare-fn)) ; Search in right subtree
        (t tree))) ; Key found

;; Function to find the minimum key in the BST
(defun bst-minimum (tree)
  (if (null (lc tree))
      tree
    (bst-minimum (lc tree))))

;; Function to find the maximum key in the BST
(defun bst-maximum (tree)
  (if (null (rc tree))
      tree
    (bst-maximum (rc tree))))

;; Helper function for bst-remove
(defun bst-transplant (tree u v)
  (if (null (parent u))
      (progn
        (when v (setf (parent v) nil))
        v)
    (progn
      (if (eq u (lc (parent u)))
          (setf (lc (parent u)) v)
        (setf (rc (parent u)) v))
      (when v (setf (parent v) (parent u)))
      tree)))

(defun bst-remove (tree key compare-fn)
  (let ((z (bst-find key tree compare-fn)))
    (cond
     ((null z) tree)  ; Key not found, return the tree as is
     ((null (lc z))   ; Z has no left child
      (bst-transplant tree z (rc z)))
     ((null (rc z))   ; Z has no right child
      (bst-transplant tree z (lc z)))
     (t               ; Z has both children
      (let* ((y (bst-minimum (rc z)))  ; Find the minimum node in the right subtree
             (tree (if (not (eq y (rc z)))
                       (bst-transplant tree y (rc y))
                     tree)))
        (setf (rc y) (rc z))
        (setf (parent (rc z)) y)
        (bst-transplant tree z y)
        (setf (lc y) (lc z))
        (setf (parent (lc z)) y)
        tree)))))  ; Return the modified tree

打印及使用

;; Function to print the BST in a simple format
(defun print-bst (tree indent)
  (when tree
    (print-bst (rc tree) (concatenate 'string indent "    ")) ; Print right subtree
    (format t "~%~A~A" indent (key tree)) ; Print the current node
    (print-bst (lc tree) (concatenate 'string indent "    ")))) ; Print left subtree

;; Example usage
(defvar my-bst nil) ; Initialize an empty BST

;; Insert elements
(format t "Inserting 10, 5, 15, 8 into the BST:")
(setq my-bst (bst-insert 10 my-bst #'<))
(setq my-bst (bst-insert 5 my-bst #'<))
(setq my-bst (bst-insert 15 my-bst #'<))
(setq my-bst (bst-insert 8 my-bst #'<))
(print-bst my-bst "")

;; Find an element
(format t "~%~%Finding 8 in the BST:")
(let ((found-node (bst-find 8 my-bst #'<)))
  (if found-node
      (format t "Found node with key: ~A" (key found-node))
    (format t "Key not found")))

;; Remove an element
(format t "~%~%Removing 5 from the BST:")
(setq my-bst (bst-remove my-bst 5 #'<))
(print-bst my-bst "")

;; Find minimum and maximum
(format t "~%~%Finding minimum in the BST:")
(format t "Minimum key: ~A" (key (bst-minimum my-bst)))

(format t "~%~%Finding maximum in the BST:")
(format t "Maximum key: ~A" (key (bst-maximum my-bst)))

当我运行此程序时，出现以下错误：

TYPE-ERROR: NIL is not of type NODE

此错误发生在执行

bst-minimum

或

bst-maximum

期间。我怀疑这个问题可能与我处理空子树的方式有关，但我不确定如何修复它。

此外，我想增强在每次插入、删除或搜索操作后打印 BST 的功能。但是，我找不到完整打印树结构的方法。

Answer 1

问题出在第一个函数的第一行。在

bst-insert

中，当您尝试插入空树时，您会调用

make-node

但立即丢弃结果并返回

tree

（函数参数）。

您必须将

bst-insert

的第一个分支修改为

(setf tree (make-node :key key :lc nil :rc nil))