Common Lisp二叉搜索树实现中的类型错误排查与打印优化

一、修复TYPE-ERROR: NIL is not of type NODE问题 #

问题根源 #

bst-minimum和bst-maximum函数未处理**空树（传入nil）**的场景，直接尝试访问节点的左/右子节点。当树为空时，tree是nil而非NODE类型，触发类型错误；递归过程中若子树为空，也会出现同样问题。

修复后的代码 #

修改最值查找函数，先判断当前树是否为空，再执行递归逻辑：

;; 查找BST中的最小节点
(defun bst-minimum (tree)
  (if (null tree)
      nil  ; 空树返回nil
      (if (null (lc tree))
          tree
          (bst-minimum (lc tree)))))

;; 查找BST中的最大节点
(defun bst-maximum (tree)
  (if (null tree)
      nil  ; 空树返回nil
      (if (null (rc tree))
          tree
          (bst-maximum (rc tree)))))

安全调用方式 #

调用时先判断返回值是否为nil，避免后续访问(key ...)触发错误：

(format t "~%~%Finding minimum in the BST:")
(let ((min-node (bst-minimum my-bst)))
  (if min-node
      (format t "Minimum key: ~A" (key min-node))
      (format t "Tree is empty, no minimum")))

(format t "~%~%Finding maximum in the BST:")
(let ((max-node (bst-maximum my-bst)))
  (if max-node
      (format t "Maximum key: ~A" (key max-node))
      (format t "Tree is empty, no maximum")))

二、增强功能：操作后自动打印树结构 #

方案1：封装操作包装函数 #

编写通用函数，执行插入/删除操作后自动打印树结构，避免重复代码：

;; 执行BST操作并打印结果
(defun bst-operate-and-print (tree operation-fn &rest args)
  (let ((new-tree (apply operation-fn args)))
    (format t "~%Tree after operation:")
    (print-bst new-tree "")
    new-tree))

使用示例 #

修改原调用逻辑，用包装函数简化操作：

(defvar my-bst nil) ; 初始化空BST

;; 插入元素
(format t "Inserting 10, 5, 15, 8 into the BST:")
(setq my-bst (bst-operate-and-print my-bst #'bst-insert 10 my-bst #'<))
(setq my-bst (bst-operate-and-print my-bst #'bst-insert 5 my-bst #'<))
(setq my-bst (bst-operate-and-print my-bst #'bst-insert 15 my-bst #'<))
(setq my-bst (bst-operate-and-print my-bst #'bst-insert 8 my-bst #'<))

;; 删除元素
(format t "~%~%Removing 5 from the BST:")
(setq my-bst (bst-operate-and-print my-bst #'bst-remove my-bst 5 #'<))

方案2：优化打印函数（可选） #

调整打印格式，标记空节点让树结构更直观：

;; 直观打印BST结构，标记空节点
(defun print-bst (tree indent)
  (if tree
      (progn
        (print-bst (rc tree) (concatenate 'string indent "    "))
        (format t "~%~A└── ~A" indent (key tree))
        (print-bst (lc tree) (concatenate 'string indent "    ")))
      (format t "~%~A└── [EMPTY]" indent)))

完整修复后的核心代码 #

;; 定义BST节点结构
(defstruct (node (:conc-name nil))
  key     ; 节点存储的键值
  (lc nil) ; 左子节点
  (rc nil) ; 右子节点
  (parent nil)) ; 父节点

;; 插入键值到BST
(defun bst-insert (key tree compare-fn)
  (cond ((null tree) 
         (make-node :key key :lc nil :rc nil)) ; 空树则创建新节点
        ((funcall compare-fn key (key tree)) 
         (setf (lc tree) (bst-insert key (lc tree) compare-fn))) ; 插入左子树
        (t 
         (setf (rc tree) (bst-insert key (rc tree) compare-fn)))) ; 插入右子树
  tree)

;; 在BST中查找键值
(defun bst-find (key tree compare-fn)
  (cond ((null tree) nil) ; 未找到
        ((funcall compare-fn key (key tree)) (bst-find key (lc tree) compare-fn)) ; 左子树查找
        ((funcall compare-fn (key tree) key) (bst-find key (rc tree) compare-fn)) ; 右子树查找
        (t tree))) ; 找到节点

;; 查找BST中的最小节点
(defun bst-minimum (tree)
  (if (null tree)
      nil
      (if (null (lc tree))
          tree
          (bst-minimum (lc tree)))))

;; 查找BST中的最大节点
(defun bst-maximum (tree)
  (if (null tree)
      nil
      (if (null (rc tree))
          tree
          (bst-maximum (rc tree)))))

;; BST移植辅助函数
(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)))

;; 从BST中删除键值
(defun bst-remove (tree key compare-fn)
  (let ((z (bst-find key tree compare-fn)))
    (cond
     ((null z) tree)  ; 未找到键值，返回原树
     ((null (lc z))   ; Z无左子节点
      (bst-transplant tree z (rc z)))
     ((null (rc z))   ; Z无右子节点
      (bst-transplant tree z (lc z)))
     (t               ; Z有两个子节点
      (let* ((y (bst-minimum (rc z)))  ; 找右子树最小节点
             (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)))))

完整使用示例 #

;; 直观打印BST结构
(defun print-bst (tree indent)
  (if tree
      (progn
        (print-bst (rc tree) (concatenate 'string indent "    "))
        (format t "~%~A└── ~A" indent (key tree))
        (print-bst (lc tree) (concatenate 'string indent "    ")))
      (format t "~%~A└── [EMPTY]" indent)))

;; 执行操作并打印树结构的包装函数
(defun bst-operate-and-print (tree operation-fn &rest args)
  (let ((new-tree (apply operation-fn args)))
    (print-bst new-tree "")
    new-tree))

;; 示例使用
(defvar my-bst nil)

(format t "=== Inserting elements ===")
(setq my-bst (bst-operate-and-print my-bst #'bst-insert 10 my-bst #'<))
(setq my-bst (bst-operate-and-print my-bst #'bst-insert 5 my-bst #'<))
(setq my-bst (bst-operate-and-print my-bst #'bst-insert 15 my-bst #'<))
(setq my-bst (bst-operate-and-print my-bst #'bst-insert 8 my-bst #'<))

(format t "~%=== Finding element 8 ===")
(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")))

(format t "~%=== Removing element 5 ===")
(setq my-bst (bst-operate-and-print my-bst #'bst-remove my-bst 5 #'<))

(format t "~%=== Finding minimum ===")
(let ((min-node (bst-minimum my-bst)))
  (if min-node
      (format t "~%Minimum key: ~A" (key min-node))
      (format t "~%Tree is empty")))

(format t "~%=== Finding maximum ===")
(let ((max-node (bst-maximum my-bst)))
  (if max-node
      (format t "~%Maximum key: ~A" (key max-node))
      (format t "~%Tree is empty")))

内容的提问来源于stack exchange，提问作者boss man