Добавление элемента в дерево поиска - Lisp

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

Добрый день. Нужно реализовать именованную функцию для использования. "Дерево двоичного поиска представлено многоуровневым списком вида (((...) х2 (...)) х1 ((..) х3 (...))). Реализовать функцию добавления нового значения в дерево."

Решение задачи: «Добавление элемента в дерево поиска»

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

;; Добавить узел в дерево
 
(defun add-in-tree (val tree)
  (cond ((null tree) (list nil val nil))
        ((> val (cadr tree)) (list (car tree) (cadr tree) (add-in-tree val (caddr tree))))
        (t (list (add-in-tree val (car tree)) (cadr tree) (caddr tree)))))
 
==> ADD-IN-TREE
 
;; Построить дерево из списка
 
(defun list-to-tree (lst &optional (tree nil))
  (cond ((null lst) tree)
        (t (list-to-tree (cdr lst) (add-in-tree (car lst) tree)))))
  
==> LIST-TO-TREE
 
;; Построить список из дерева
 
(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
 
;; Проверка
 
(list-to-tree '(1 2 0 -7 4 12 -4 5))
 
==> (((NIL -7 (NIL -4 NIL)) 0 NIL) 1 (NIL 2 (NIL 4 ((NIL 5 NIL) 12 NIL))))
 
(tree-to-list (list-to-tree '(1 2 0 -7 4 12 -4 5)))
 
==> (-7 -4 0 1 2 4 5 12) ;; Список отсортирован !

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

В данном коде реализованы две основные функции для работы с двоичными деревьями: «add-in-tree» и «list-to-tree», а также вспомогательная функция «tree-to-list». Функция «add-in-tree» добавляет новый узел с заданным значением в дерево. Функция использует «cond» для проверки, является ли дерево пустым. Если это так, то создается новый узел с заданным значением. В противном случае функция рекурсивно вызывается для левого поддерева, затем для правого поддерева и, наконец, для нового узла. Это гарантирует, что каждое значение в дереве уникально и каждое число в правой части дерева больше, чем в левой. Функция «list-to-tree» создает двоичное дерево из списка. Она также использует «cond» для проверки, является ли список пустым. Если это так, то возвращается пустое дерево. В противном случае функция рекурсивно вызывается для списка, добавляя каждый элемент в дерево. Функция «tree-to-list» преобразует двоичное дерево в список. Она использует «cond» для проверки, является ли дерево пустым. Если это так, то возвращается пустой список. В противном случае функция рекурсивно вызывается для дерева, добавляя каждый узел в список. В приведенном примере кода создается список со значениями 1, 2, 0, -7, 4, 12, -4 и 5. Затем этот список преобразуется в двоичное дерево с помощью функции «list-to-tree». Наконец, двоичное дерево преобразуется обратно в список с помощью функции «tree-to-list», что дает отсортированный список -7, -4, 0, 1, 2, 4, 5 и 12.