Если ещё актуально, могу сходу набросать структуру дерева и функцию вставки.
Структура такая: каждый "элемент" (я не знаком с терминологией) - cons-ячейка, где car часть - собственно значение.
cdr часть cons-ячейка, гда car содержит левую, а cdr правую ветки, если веток нет, то соотв. части равны nil.
| Код |
(defun insert-foo (tree val)
(if tree ; на передали древо или
(let ((tree-val (car tree)) ; значение в корне
(new-tree (cdr tree))) ; собственно оставшееся дерево
(if (< val tree-val) ; идём направо или налево ?
;; налево
(if (car new-tree) ; проверка, а есть ли уже левая ветка, или там пока пусто
;; ветка есть
(insert-foo (car new-tree) val) ; для наглядности используем рекурсию
;; ветки нет. создаём.
(setf (car new-tree) (cons val (cons nil nil))))
;; направо
(if (cdr new-tree) ; проверка, а есть ли уже правая ветка, или там пока пусто
;; ветка есть
(insert-foo (cdr new-tree) val) ; для наглядности используем рекурсию
;; ветки нет. создаём.
(setf (cdr new-tree) (cons val (cons nil nil)))))))
|
Для первого элемента сортируемого списка корень дерева создаём вручную.
| Код |
(let ((tree (cons (car list) (cons nil nil))))
(dolist (i (cdr list)) ; (cdr list) == (rest list) потому, что первый элемент уже обработан
(insert-foo tree i))
развёртываем дерево в новый список)
|
Правильность работы не проверял.
P.S. (cons foo nil) эквивалентно (list foo), но так как мы рассматриваем tree не как вложенный список, для понятности я писал cons.
PPS есть более "красивый" вариант в функциональной парадигме (без setf, каждый раз insert-foo создаёт новую ячейку), но он гораздо менее понятен. |