lisp - 返回完整二叉树的 LISP 函数

Question

我正在尝试做一个 lisp 函数，它将接收一个列表并返回一个完整的二叉树，其节点以相同的顺序从列表的元素中填充。
例如，

(makeTree '(4 3 9 10))
(4 (3 (9 () ()) ()) (10 () ()))

为此，我使用了一个将列表拆分为 2 的函数。因此，我所做的是尝试将列表的头部与尾部分开，然后使用拆分函数来执行二叉树。但我在实施它时遇到了麻烦。有人能帮助我吗？
到目前为止，这是我的代码：

(defun aux-head (l n)
   (if (= n 0) '()
       (cons (car l) (aux-head (cdr l)(- n 1)))))
(defun aux-tail (l n)
   (if (= n 0) l
       (aux-tail (cdr l) (- n 1))))
(defun split (lst)
   (cond
       ((null lst) '(()()))
       ((evenp (length lst))
          (list (aux-head lst (/ (length lst) 2))(aux-tail lst (/ (length lst) 2))))
       ((oddp (length lst))
          (list (aux-head lst (+ (floor (length lst) 2) 1))
                (aux-tail lst (+ (floor (length lst) 2) 1))))))
(defun make-cbtree (lst)
   (cond
       ((null lst) '(()()))
       ((car lst)
          ((split ((cdr lst)))))))

标签： lispcommon-lisp

Answer 1

创建二叉搜索树的常用方法是逐个添加项目。它可能看起来像这样：

(defun add-node (tree val)
  (if (null tree)
      (list val () ())
      (destructuring-bind (v l r) tree
        (if (< val v)
            (list v (add-node l val) r)
            (list v l (add-node r val))))))

这个将值插入到正确的位置（重建树，不可变样式）：

CL-USER> (add-node (list 1 nil nil) 2)
;; (1 NIL (2 NIL NIL))
CL-USER> (add-node (list 1 nil nil) 0)
;; (1 (0 NIL NIL) NIL)

接下来你需要的是一个一个地处理输入列表，将它添加到树中，从空的开始：

(defun make-tree (data)
  (reduce #'add-node data :initial-value nil))

CL-USER> (make-tree (list 4 3 9 10))
;; (4 (3 NIL NIL) (9 NIL (10 NIL NIL)))

您还可以编写traverse程序：

(defun traverse (tree)
  (when tree
    (append (traverse (cadr tree))
            (list (car tree))
            (traverse (caddr tree)))))

CL-USER> (traverse (make-tree (list 4 3 9 10)))
;; (3 4 9 10)