Одной из наиболее частых операций с деревом является исследование всех узлов и обработка их некоторым образом, либо поиск некоторого значения, либо поиск всех значений. Эти процедуры известны как обход дерева. Основной алгоритм для этого следующий:
1. Если дерево пусто, то ничего не делать.
2. Иначе, обработать текущее значение, затем перейти на левое подде рево, затем перейти на правое поддерево.
Как и само дерево, алгоритм является рекурсивным: он обрабатывает левое и правое поддеревья так же, как и исходное дерево. В Прологе он выражается двумя предложениями: одно для пустого, а другое для непустого дерева.
обход (empty). /* ничего не делать */
обход (tree (X, Y, Z)): —
делать что-либо с X,
обход (X),
обход (Z).
Этот алгоритм известен как поиск «сначала вглубь», так как он спускается по каждой ветви вниз, насколько возможно, прежде чем вернуться вверх для обхода другой ветви (рис.2). Чтобы посмотреть алгоритм в действии, выполните программу Lab5_1.PRO, которая обходит дерево и печатает все элементы, которые ей попадаются. Дерево, показанное на рисунках 1 и 2, Lab5_1.PRO распечатает
Катя
Миша
Вова
Лида
Люда
Зина
Петя
Можно легко приспособить программу для выполнения каких-то других операций над элементами, а не печати их.
/* Программа Lab5_1.PRO */
/* Обход дерева «сначала вглубь» и печать каждого элемента, который попадается на пути. */
domains
treetype = tree (string, treetype, treetype); empty ()
predicates
print_all_elements (treetype)
clauses
print_all_elements (empty).
print_all_elements (tree (X, Y, Z)):-
write (X), nl,
print_all_elements (Y),
print_all_elements (Z).
goal
print_all_elements (tree («Катя»,
tree («Миша»,
tree («Вова», empty, empty),
tree («Лида», empty, empty)),
tree («Люда»,
tree («Зина», empty, empty),
tree («Петя», empty, empty)))),nl,fail;true.
Поиск «сначала вглубь» прост для способа, которым Пролог ищет базу знаний. Он организует предложения в дерево и проходит каждое поддерево, пока предложения не закончатся. Если бы вы захотели, то могли бы описать дерево посредством набора прологовских правил, таких как:
мать(«Катя», «Люда»).
мать(«Катя», «Миша»).
отец(«Миша», «Вова»).
отец(«Миша», «Лида»)….
Это было бы предпочтительнее, если бы дерево предназначалось только для выражения родственных связей между людьми. Но, такой вид описания делает невозможным обработку всего дерева как единой, сложной структуры данных. Как вы увидите, комплексные структуры данных бывают весьма полезными, так как они упрощают сложные вычислительные задачи.
Создание дерева
Один из способов создания дерева — это запись ячеистой структуры функторов и аргументов, как в предыдущем примере Lab5_1.PRO. Однако, в общем случае Пролог создает дерево путем вычисления. На каждом шаге, пустое поддерево заменяется непустым в процессе Прологовского объединения (подбор по агрументам).
Создание дерева из одного узла присвоением исходного данного тривиально:
create_tree (N, tree (N, empty, empty)).
Здесь говорится: » Если N — данное, то tree (N, empty, empty) — это дерево из одного узла, содержащее его».
Построение структуры дерева так же просто. Следующей процедуре нужны три дерева в качестве аргументов. Она вставляет первое дерево в качестве левого поддерева во второе дерево и результат этого присваивает третьему дереву:
insert_left (X, tree (A, _, B), tree (A, X, B)).
Заметьте, что в этом предложении нет тела, то есть нет четких шагов при его выполнении. Все, что должен сделать компьютер — это соединить аргументы друг с другом в правильном порядке — и работа закончена.
Для примера предположим, что вы хотите вставить дерево
(«Миша», empty, empty) в качестве левого поддерева для дерева («Катя», empty, empty). Чтобы это сделать, надо выполнить целевое утверждение
insert_left (tree («Миша», empty, empty),
tree («Катя», empty, empty),
T)
и T немедленно примет значение:
tree («Катя», tree («Миша», empty, empty), empty).
Здесь показан способ построения дерева шаг за шагом. Этот же способ показан в программе Lab5_2.PRO. В действительности, элементы, которые надо добавить к дереву могут приходить с внешнего входа.
/* Программа Lab5_2.PRO */
/* Простые процедуры построения дерева
create_tree (A, B) помещает A в поле данных одноузлового
дерева B
insert_left (A, B, C) вставляет A как левое поддерево B
и присваивает результат C
insert_right (A, B, C) вставляет A как правое поддерево
B и присваивает результат C */
domains
treetype = tree (string, treetype, treetype); empty ()
predicates
create_tree (string, treetype)
insert_left (treetype, treetype, treetype)
insert_right (treetype, treetype, treetype)
clauses
create_tree (A, tree (A, empty, empty)).
insert_left (X, tree (A, _, B), tree (A, X, B)).
insert_right (X, tree (A, B, _), tree (A, B, X)).
goal
/* Сначала создадим несколько одноузловых деревьев*/
create_tree («Вова», V),
create_tree («Лида», Ld),
create_tree («Миша», M),
create_tree («Зина», Z),
create_tree («Петя», P),
create_tree («Люда», L),
create_tree («Катя», K),
/*…затем соединим их… */
insert_left (V, M, M2),
insert_right (Ld, M2, M3),
insert_left (Z, L, L2),
insert_right (P, L2, L3),
insert_left (M3, K, K2),
insert_right (L3, K2, K3),
/*…и печатаем результат. */
write (K3), nl,fail;true.
В Прологе нет возможности изменить значение переменной после того как присвоение произошло. Поэтому в программе Lab5_2.PRO используется так много имен переменных; каждый раз, когда нужно получить новое значение, требуется новая переменная. Но, обычно, большое число имен переменных не нужно, так как в общем случае повторяющиеся процедуры получают новые переменные, вызывая себя рекурсивно, и каждый вызов имеет определенный набор переменных.
Бинарные поисковые деревья
Итак, мы использовали дерево для представления отношений между элементами. Это, конечно, не самый лучший вид использования деревьев, так как Прологовские предложения могут выполнить такую же работу. Но, деревья можно использовать и иначе.
В деревьях имеется возможность так хранить данные, что их можно быстро найти. Дерево построенное для такой цели называется поисковым деревом. С точки зрения пользователя, сама структура дерева не несет информации, дерево — это просто более быстрая альтернатива списку или массиву. Вспомним, что при обходе обычного дерева, вы рассматриваете текущий узел, а затем оба его поддерева. Чтобы найти определенное значение, вы должны рассмотреть каждый узел всего дерева.
Время, затрачиваемое на поиск в обычном дереве из N элементов, в среднем пропорционально N.
Бинарное поисковое дерево строится таким образом, что глядя на любой узел можно предсказать, в каком из его узлов находится заданное значение. Это делается заданием отношения порядка между значениями, таким как алфавитный или пронумерованрый порядок. Значения в левом поддереве предшествуют значению в текущем узле и следуют после правого поддерева. На рисунке 3 показан пример. Заметьте, что те же имена установленные в другом порядке дадут другое дерево
Рисунок 3: Бинарное поисковое дерево
Как только вы посмотрите во время поиска на узел бинарного поискового дерева, вы можете исключить из рассмотрения половину оставшихся узлов и провести поиск очень быстро. Если теперь размер дерева увеличить вдвое, то для поиска потребуется только один дополнительный шаг.
Время, требуемое для поиска значения на бинарном поисковом дереве, в среднем пропорционально log2N (а, в действительности, пропорционально logN по любому основанию).
Чтобы построить дерево, нужно начать с пустого дерева и добавлять к нему значения одно за другим. Процедура добавления значения такая же, как при поиске: необходимо просто найти место, где оно должно находится и вставить его туда. Этот алгоритм заключается в следующем:
1. Если текущее после узла поддерево — есть пустое дерево, то вставить в него значение.
2. Иначе, сравнить значение, которое необходимо вставить со значением в текущем узле. Вставить значение в левое или правое поддерево, в зависимости от результата сравнения.
В Прологе этому алгоритму нужно три предложения — по одному на каждый случай. первое предложение таково:
insert (NewItem, empty, tree (NewItem, empty, empty): -!.
На естественный язык эта запись переводится так: » Результатом вставки NewItem (нового значения) в empty (пустое дерево) будет дерево tree (NewItem, empty, empty).» Восклицательный знак говорит, что если это предложение можно успешно применить, то другие предложения проверять не надо.
Второе и третье предложения осуществляют вставку в непустые деревья:
insert (NewItem, tree (Element, Left, Right), tree (Element, NewLeft, Right): —
NewItem < Element,!, insert (NewItem, Left, NewLeft).
insert (NewItem, tree (Element, Left, Right), tree (Element, Left, NewRight): —
insert (NewItem, Right, NewRight).
Если NewItem < Element, то вы вставляете его в левое поддерево, а если иначе, то вставляете его в правое поддерево. Заметьте, что третье предложение будет выполняться, если не подошло ни одно из первых двух. Заметьте так же, как много работы надо проделать в начале предложения, чтобы подобрать аргументы.
Сортировка на основе дерева
После того, как дерево построено, можно легко переставить все его элементы в алфавитном порядке. Алгоритм для этого — вариант поиска сначала вглубь:
1. Если дерево пустое, то ничего не делать.
2. Иначе, переставить все элементы левого поддерева, затем текущий элемент, затем все элементы правого поддерева.
Или, в Прологе:
retrieve_all (empty). /* Ничего не делать */
retrieve_all (tree (Item, Left, Right)): —
retrieve_all (Left),
do_something_to (Item),
retrieve_all (Right).
Сортировку, следующих друг за другом значений, можно выполнить вставляя их в дерево, и затем, перестановкой их по порядку. Для N значений это займет время, пропорциональное N?logN, так как вставка и перестановка занимают время, пропорциональное logN, причем, то и другое должно быть выполнено N раз. Это самый быстрый сортирующий алгоритм, известный на сегодня.
Пример: Программа Lab5_3.PRO использует описанный способ для расстановки по алфавиту вводимых символьных значений.
Замечание 1: В этом примере используются некоторые стандартные предикаты Турбо Пролога для чтения с клавиатуры. Предикат readint — целые, а readchar — символьные значения.
Замечание 2: В программе lab5_3_1.pro – та же программа, но с использованием окон, меню и поэлементным выводом дерева. К тому же, в этом примере стандартный предикат exit останавливает вычисления.
/* Lab5_3.pro */
domains
chartree = tree(char, chartree, chartree); end
predicates
create_tree(chartree, chartree)
insert(char, chartree, chartree)
goal
create_tree(end,NT),
write(NT),nl,fail;true.
clauses
create_Tree(Tree, NewTree):-
readchar(C),
C<>’#’,!,
write(C, » «),
insert(C, Tree, TempTree),
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).
Загрузите и запустите программы Lab5_3.PRO, Lab5_3_1.PRO и понаблюдайте, как Турбо Пролог выполнит сортировку символьной последовательности на основе дерева.
Задания:
1. Найти максимальный элемент дерева.
2. Вычисление глубины дерева
3. Считать элементы заданного дерева в список:
а) при обходе «в глубину»;
б) *при обходе «в ширину»;
4. Поиск пути от корня до заданного элемента:
а) в виде последовательности элементов;
б) в виде списка.
5*. Обход дерева «в ширину» и вывод пути в виде последовательности элементов.
6*. Отображение дерева в обычной форме. Например, чтобы дерево
tree («Катя»,
tree («Миша»,
tree («Вова», empty, empty),
tree («Лида», empty, empty)),
tree («Люда»,
tree («Зина», empty, empty),
tree («Петя», empty, empty)))
было показано как на рис.1 или в виде досовского дерева каталогов рис.4.
|_
| |_____
| |
| |_____
|__
рис.4.
7. Подсчитать число вершин дерева.
8. Подсчитать число листьевых вершин дерева.
9. Подсчитать число вершин дерева, значения которых лежат в определенном задаваемом диапазоне.
10. Определить, является ли дерево Т1 поддеревом дерева Т.
11. Вывести самую длинную ветвь дерева в виде последовательности вершин или списка вершин.
12. Определить отношение sum_tree(Tree_of_integer, Sum), выполненное, если число Sum равно сумме целых чисел, являющихся вершинами дерева Tree_of_integer.
13. Определить, является ли дерево Т упорядоченным деревом целых чисел, т. е. для любого узла должно выполняться .
14. Найти среднее арифметическое листьевых вершин дерева.
15. Найти среднее арифметическое отрицательных узлов дерева.
