用于构建二叉搜索树的LISP函数无法运行，请求排查原因

核心问题：参数传递与逻辑错误 #

你的代码主要有两个致命问题：

1. 参数传递方式误解：LISP函数参数是按值传递的，你在函数里直接(setf tree ...)只会修改局部变量，无法影响外部的tree变量。比如第一次插入8时，函数内部的tree被修改，但外部的tree还是初始的(NIL . NIL)。
2. 子树判断逻辑错误：判断左子树是否为空时用了(null (caaddr tree))，这完全是错误的——caaddr取的是右子树的根节点，和左子树毫无关系。

修复后的代码 #

调整树结构为标准的(根节点 左子树 右子树)列表形式，同时修改函数逻辑确保修改能同步到外部变量：

(defun insert-bst (element tree)
  (cond
    ;; 空树：直接初始化根节点
    ((null (car tree))
     (setf (car tree) element
           (cadr tree) (list nil nil nil)
           (caddr tree) (list nil nil nil)))
    ;; 元素大于等于根节点，处理右子树
    ((>= element (car tree))
     (if (null (car (caddr tree)))
         ;; 右子树为空，创建新节点
         (setf (car (caddr tree)) element
               (cadr (caddr tree)) (list nil nil nil)
               (caddr (caddr tree)) (list nil nil nil))
         ;; 递归插入右子树
         (insert-bst element (caddr tree))))
    ;; 元素小于根节点，处理左子树
    ((< element (car tree))
     (if (null (car (cadr tree)))
         ;; 左子树为空，创建新节点
         (setf (car (cadr tree)) element
               (cadr (cadr tree)) (list nil nil nil)
               (caddr (cadr tree)) (list nil nil nil))
         ;; 递归插入左子树
         (insert-bst element (cadr tree))))))

;; 初始化空树
(setf tree (list nil nil nil))
(print tree)
(insert-bst 8 tree)
(insert-bst 3 tree)
(insert-bst 6 tree)
(insert-bst 4 tree)
(insert-bst 7 tree)
(print tree)

关键修改说明 #

• 初始化树为(nil nil nil)，方便直接修改根节点、左子树、右子树的结构。
• 不再直接给函数参数赋值，而是用setf修改tree的car/cadr/caddr部分，确保修改能同步到外部变量。
• 修正子树判断逻辑，直接检查子树的根节点是否为空。
• 函数名改为insert-bst，更符合二叉搜索树插入操作的语义。

运行后最终输出的树结构为：

(NIL NIL NIL)
(8 (3 NIL (6 (4 NIL NIL) (7 NIL NIL))) NIL)

完全符合二叉搜索树的结构要求。

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