Бинарные деревья
Программа 3.22. Быстрая сортировка.
и разбиение списка Xs в соответствии с Y дает списки Littles и Bigs”. Второе предложение для отношения partition понимается аналогично. Исходный факт пустой список разбивается на два пустых списка.
Следующий рекурсивный тип данных который мы рассмотрим, – бинарные деревья. Такие структуры имеют важное значение во многих алгоритмах.
Бинарные деревья задаются с помощью тернарного функтора tree (Element,Left,Right), где Element – элемент, находящийся в вершине, а Left и Right – соответственно левое и правое поддерево. Пустое дерево изображается атомом void. Например, дерево
может быть задано как tree (a,tree(b,void,void), tree (c,void,void)).
Логические программы, работающие с бинарными деревьями, подобны программам, работающим со списками. Как и в случаях натуральных чисел и списков, начнем с типового определения бинарного дерева. Оно дается программой 3.23.
binary-tree(Tree) ¬
Tree-бинарноедерево.
binary_tree(void).
binary_tree(tree(Element,Left,Right)) binary_tree(Left),binary_tree(Right).
Программа 3.23. Определение бинарного дерева.
Отметим, что программа – с двойной рекурсией, т.е. в теле рекурсивного правила имеются две цели с тем же предикатом, что и в заголовке правила. Этот эффект вникает благодаря двойной рекурсивной природе бинарных деревьев и может быть замечен и в остальных программах данного раздела.
Давайте напишем некоторые программы обработки деревьев. Наш первый пример состоит в проверке, появляется ли некоторый элемент в дереве. Реляционная схема – tree_member(Element, Tree}. Отношение выполнено, если элемент Element является однойиз вершин дерева Tree. В программе 3.24 приведено определение. Декларативное понимание программы: “Х – элемент дерева, если Х находится в вершине (согласно факту), или Х – элемент левого или правого поддерева (согласно двум рекурсивным правилам)”.
tree-member (Element,Tree) *-
Element является элементом бинарного дерева Tree.
tree.member(X,tree(X,Left,Right)).
tree_member(X,tree(Y,Left,Right)) ¬ tree_member(X,,Left).
tree_member(X,tree(Y,Left,Right)) ¬ tree_member(X,Right).
Программа 3.24. Проверка принадлежности дереву.
Две ветви бинарного дерева различны, но во многих приложениях это различие несущественно. Следовательно, возникает полезное понятие изоморфизма, которое определяет, являются ли два неупорядоченных дерева по существу одинаковыми. Два бинарных дерева Т1 и Т 2 изоморфны,если Т2 может быть получено из Т1 изменением порядка ветвей в поддеревьях. На рис. 3.6 изображены три простых бинарных дерева. Первые два изоморфны, третье не изоморфно им.
Изоморфизм является отношением эквивалентности с простым рекурсивным определением. Два пустых дерева изоморфны. В случае непустых деревьев два дерева изоморфны, если элементы в вершинах дерева совпадают, и/или оба левых поддерева и оба правых поддерева изоморфны, или левое поддерево одного дерева изоморфно правому поддереву другого и два других поддерева тоже изоморфны.
Рис. 3.6. Сравнение деревьев с точностью до изоморфизма.
Программа 3.25 определяет предикат isotree(Treel,Tree2), который истинен, если дерево Tree1 изоморфно дереву Тгее2. Аргументы входят в предикат симметрично. Программы, относящиеся к бинарным деревьям, используют двойную рекурсию
isotree( Tree1,Tree2)
бинарные деревья Treel и Тгее2 изоморфны.
isotree(void,void).
isotree(tree(X,Leftl,Right1),tree(X,Left2,Right2))¬
isotree(Left],Left2),isotree(Rightl,Righl2).
isotree(tree(X,Leftl,Right l),tree(X,Left2,Right2))¬
isotreet Leftl,Right2),isotree( Right1,Left2).
Программа 3.25. Определение изоморфизма деревьев.
по одной на каждую ветвь дерева. Двойная рекурсия может проявляться двумя способами. В программе могут рассматриваться два отдельных случая, как в программе 3.24 для отношения tree_member. В отличие от этого программа 3.12 проверяющая принадлежность элемента списку, содержит лишь один рекурсивный случай. При другом способе в теле рекурсивного правила содержатся два рекурсивных вызова, как в каждом рекурсивном правиле для isotree в программе 3.25.
Задание упражнения 3.3 (1) состоит в том, чтобы написать программу подстановки элементов в списки. Аналогичная программа может быть написана для подстановки элементов в бинарные деревья. Предикат substitute(X,Y,OldTree,NewTree) выполнен, если дерево NewTree получается из дерева ОIdTree заменой всех вхождений элемента Х на Y. Аксиоматизация отношения substitute/4 приведена в программе 3.26.
substitute (X,Y,TreeX,TreeY) ¬
бинарное дерево TreeY – результат замены всех вхождений Х в бинарном дереве ТгееХ на Y
substitule(X,Y,void,void). substitute(X,Y,tree(X,Left,Right),tree(Y,Leftl,Rightl)) ¬
substitute(X,Y,Left,Left1),
substitute(X,Y,Right,Right1). substitute(X,Y,tree(Z,Left,Right), tree(Z,Leftl,Right 1))¬
X¹Z,
substitute(X,Y,Left,Leftl),
substitute(X,Y,Right, Right 1)
Программа 3.26. Подстановка терма в дерево.
Во многих приложениях, использующих деревья, требуется доступ к элементам, указанным в вершинах. Основной является идея обхода дерева в предписанном порядке. Имеются три возможности линейного упорядочения при обходе: сверху вниз, когда сначала идет значение в вершине, далее вершины левого поддерева. затем вершины правого поддерева; слева направо, когда сначала приводятся вершины левого поддерева, затем вершина дерева и далее вершины правого поддерева: и наконец, снизу вверх, когда значение в вершине приводится после вершин левого и правого поддерева,
Определение каждого из этих трех обходов приведено в программе 3.27. Рекурсивная структура определений одинакова, единственное отличие состоит в порядке элементов, полученных применением целей вида append.
pre_order(Tree.Pre) ¬
Prе-обход бинарного дерева Tree сверху вниз.
pre,order{tree(X,L,R),Xs) ¬
pre_order(L,Ls),pre_order(R,Rs),append([X | Ls],Rs,Xs).
pre_order(void,[ ]).
in_order(Tree.In) ¬
In- обход бинарного дерева Tree слева направо.
in_order(tree(X,L,R),Xs) ¬
in_order(L,Ls),in_order(R,Rs),append(Ls,[X | Rs],Xs). in_order(void,[ ]).
post_order-(Tree, Post) ¬
Post - обход бинарного дерева Tree снизу вверх.
post_order(tree(X,L,R),Xs) ¬
post_order(L,Ls),
post„order(R,Rs),
append(Rs,[X],Rsl),
append(Ls,Rsl,Xs).
post_order(void,[ ]).
Программа 3.27. Обходы бинарного дерева.