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

Формулировка задачи:

Определить функцию (ДОБАВЬ а дерево), которая добавляет в упорядоченное дерево (дерево) элемент а. (Подсказка: копировать дерево по пути поиска и подправлять нужное поддерево). Если изначально дерево не пустое: (setq tree '(90 0 100)), то нужно добавить в это дерево новый элемент.

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

Листинг программы

;; Добавить 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)

Объяснение кода листинга программы

В данном коде определена функция add-in-tree, которая добавляет элемент a в упорядоченное дерево tree. Алгоритм работы функции следующий:

Если дерево пустое, то возвращается новое дерево, состоящее из одного элемента — a.
Если a больше элемента, находящегося в корне дерева, то рекурсивно вызывается функция для правой части дерева.
Если a меньше или равно корню дерева, то рекурсивно вызывается функция для левой части дерева, а в качестве третьего аргумента передается результат вызова функции для правой части дерева. Также в коде определена функция tree-to-list, которая преобразует дерево в список. Алгоритм работы функции следующий:
Если дерево пустое, то возвращается nil.
Если узел дерева не является листовым, то в список добавляются значения, полученные при вызове функции для левого поддерева, корня и правого поддерева. В конце кода вызывается функция tree-to-list для преобразования дерева в список и выводится результат.