Определить функцию, которая добавляет в упорядоченное дерево элемент а

;; Добавить a в упорядоченное дерево tree
 
(defun add-in-tree (a tree)
  (cond ((null tree) (list nil a nil))
        ((> a (cadr tree)) (list (car tree) (cadr tree) (add-in-tree a (caddr tree))))
        (t (list (add-in-tree a (car tree)) (cadr tree) (caddr tree)))))
 
==> add-in-tree
 
 
;; Создание пустого дерева
 
(setq *tree* nil)
 
==> NIL
 
;; добавим 5
 
(setq *tree* (add-in-tree 5 *tree*))
 
==> (NIL 5 NIL)
 
;; добавим 6
 
(setq *tree* (add-in-tree 6 *tree*))
 
==> (NIL 5 (NIL 6 NIL))
 
;; добавим 0
 
(setq *tree* (add-in-tree 0 *tree*))
 
==> ((NIL 0 NIL) 5 (NIL 6 NIL))
 
;; добавим 1
 
(setq *tree* (add-in-tree 1 *tree*))
 
==> ((NIL 0 (NIL 1 NIL)) 5 (NIL 6 NIL))
 
;; добавим 8
 
(setq *tree* (add-in-tree 8 *tree*))
 
==> ((NIL 0 (NIL 1 NIL)) 5 (NIL 6 (NIL 8 NIL)))
 
;; Преобразовать дерево в список (порядок обхода: левое - корень - правое)
 
(defun tree-to-list (tree)
  (cond ((null tree) nil)
        (t (append (tree-to-list (car tree)) (list (cadr tree)) (tree-to-list (caddr tree))))))
 
==> tree-to-list
 
;; Проверка
 
(tree-to-list *tree*)
 
==> (0 1 5 6 8)