Ребят, помогите, пожалуйста, с задачей по Лиспу:
реализовать алгоритм сортировки вставками в бинарном дереве (без сбалансировки)
Что-то у меня вобще никак лисп не идёт((((
Буду очень благодарна

Для «обыкновенного» списка сортировка вставками выглядит, вероятно, так:

Как устроено Ваше бинарное дерево?

Это сообщение отредактировал(а) VH_ - 23.9.2009, 07:32

Это лаба, и, впринципе, о каких-то усобых условиях для дерева ничего не оговаривается... Спасибо за помощь)))

Вы можете словесно изложить алгоритм "сортировки вставками" именно "в бинарном дереве" (либо дать ссылку на такое описание)?

Так вот в том-то и дело, что гугл даже в теории такого не знает, я уточню в универе и отпишу, а то понятно только то, что ничего не понятно

В общем, вводим список, а потом по нему проходим - на каждом шаге элемент вставляем в дерево, начиная с корня, дальше - если следующий элемент больше, чем элемент в корне, идём на правую ветку, иначе - в левую, и так до листа, а тудо вставляем данный элемент. И дальше нужно вывести уже отсортированный список через отдельную функцию

Если ещё актуально, могу сходу набросать структуру дерева и функцию вставки.
Структура такая: каждый "элемент" (я не знаком с терминологией) - cons-ячейка, где car часть - собственно значение.
cdr часть cons-ячейка, гда car содержит левую, а cdr правую ветки, если веток нет, то соотв. части равны nil.



Для первого элемента сортируемого списка корень дерева создаём вручную.


Правильность работы не проверял. 

P.S. (cons foo nil) эквивалентно (list foo), но так как мы рассматриваем tree не как вложенный список, для понятности я писал cons.
PPS есть более "красивый"  вариант в функциональной парадигме (без setf, каждый раз insert-foo создаёт новую ячейку), но он гораздо менее понятен.

Это сообщение отредактировал(а) lonli - 26.9.2009, 11:43

Разве это может быть «гораздо менее понятно»?

Развертывание дерева в линейный список:

Спасибо Вам огромное за помощь)