Сортировка на основе дерева

После того, как дерево построено, можно легко переставить все его

элементы в алфавитном порядке. Алгоритм для этого - вариант поиска снача-

ла вглубь:

1. Если дерево пустое, то ничего не делать.

2. Иначе, переставить все элементы левого поддерева, затем текущий

элемент, затем все элементы правого поддерева.

Или, в Прологе:

retrieve_all(empty). /* Ничего не делать */

retrieve_all(tree(Item, Left, Right)) :-

retrieve_all(Left),

do_something_to(Item),

retrieve_all(Right).

Сортировку, следующих друг за другом значений, можно выполнить

вставляя их в дерево, и затем, перестановкой их по порядку. Для N значе-

ний это займет время, пропорциональное N log N, так как вставка и перес-

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

но быть выполнено N раз. Это самый быстрый сортирующий алгоритм, извест-

ный на сегодня.

Пример

Программа CH07EX11.PRO использует описанный способ для расстановки

по алфавиту вводимых символьных значений.

Замечание: В этом примере используются некоторые стандартные преди-

каты Турбо Пролога для чтения с клавиатуры. Предикат readint - целые, а

readchar - символьные значения. Эти предикаты подробно рассмотрены в Гла-

ве 12. К тому же, в этом примере стандартный предикат exit останавливает

вычисления. Он кроме этого выполняет еще много чего, и если вы хотите уз-

нать подробнее об exit, то смотрите Главу 19.

/* Программа CH07EX11.PRO */

domains

chartree = tree(char, chartree, chartree); end

predicates

do(chartree)

action(integer,chartree,chartree)

create_tree(chartree,chartree)

insert(char,chartree,chartree)

write_tree(chartree)

repeat

goal

do(end)

clauses

do(Tree):-

makewindow(1,7,7,"character tree sort",0,0,20,60),

repeat,

clearwindow,

write("Enter 1 to create a tree\n"),

write("Enter 2 to show tree\n"),

write("Enter 7 to exit\n"),

readint(X),

action(X,Tree, NewTree),

do(NewTree).

action(1,Tree,NewTree):-

write("Enter characters or # to end: "),

create_Tree(Tree,NewTree).

action(2,Tree,Tree):-

write_Tree(Tree),

write("\nPress a key to continue"),

readchar(_).

action(7,_,end):- exit.

create_Tree(Tree,NewTree):-

readchar(C),

C<>'#',!,

write(C," "),

insert(C,Tree,NewTree),

create_Tree(TempTree,NewTree).

create_Tree(Tree,Tree).

insert(New,end,tree(New,end,end)):-!.

insert(New,tree(Element,Left,Right),

tree(Element,NewLeft,Right)):-

New<Element, !,

insert(New,Left,NewLeft).

insert(New,tree(Element,Left,Right),

tree(Element,Left,NewRight)):-

insert(New,Right,NewRight).

write_Tree(end).

write_Tree(tree(Item,Left,Right)):-

write_Tree(Left),

write(Item," "),

write_Tree(Right).

repeat.

repeat:-repeat.

Загрузите и запустите программу CH07EX11.PRO и понаблюдайте, как

Турбо Пролог выполнит сортировку символьной последовательности на основе

дерева.