lisp - 在 Lisp 中构建二叉树

Question

我正在尝试用 lisp 构建一棵二叉树。该函数应该执行此操作

(buildBST  ‘(6 9 2 1 7))  -> (6  (2 (1) ()) (9 (7) ())) 

我们到目前为止的代码将不断返回错误

> 7 nil arguments should be of type real

这是我们的代码

(defun buildBst (lis)
    (cond 
        ((null lis) 0)
        ((atom lis) lis)
        (t (if ( >(car lis)(car(cdr lis)))
                (buildBst( cdr lis))
                (buildBst(cdr lis))))))

Answer 1

最好的方法是创建一个插入函数:

(defun tree-insert-element (tree element)
  (cond ((tree-null-p tree) 
         (make-tree element nil nil))
        ((< (tree-value tree) element) 
         (make-tree (tree-value tree)
                    (tree-left tree)
                    (tree-insert-element (tree-right tree) element)))
        (t 
         (make-tree (tree-value tree)
                    (tree-insert-element (tree-left tree) element)
                    (tree-right tree)))))

因此，当您想要插入一大堆时，您可以这样做:

(defun tree-insert-list (tree list)
  (reduce #'tree-insert-element list :initial-value tree))

当然，您需要定义插入函数使用的函数，因为我真的不关心您如何选择对树进行建模。从预期结果来看，我猜 make-tree 可能只是包装 list*，但这不是制作树的唯一方法!