Функция LISP, возвращающая полное двоичное дерево

#lisp #common-lisp

Вопрос:

Я пытаюсь выполнить функцию 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)))))))

1. в чем проблема с кодом?

2. Пока в коде нет ошибки, просто мне нужна помощь в понимании того, как я должен выполнить свой код, чтобы получить нужный мне результат, который представляет собой полное двоичное дерево списка

3. Я знаю, что мне нужно делать, просто я не знаю, как это сделать

4. как вы можете сказать по вводу, что результат равен (4 (3 (9 () ()) ()) (10 () ())) , а не (4 (3 (9 () ()) (10 () ())) ()) ? существует ли какой-либо специальный набор правил? потому что в противном случае задача неоднозначна

5. Это не я это говорю. Это то, что нас просят сделать. Я добавил изображение двоичного дерева, может быть, это может помочь

Ответ №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)