Деревья. Деревами называется граф, у которого одна вершина корневая, а остальные вершины имеют только одного отца и все вершины являются потомками корневой вершины

Деревами называется граф, у которого одна вершина корневая, а остальные вершины имеют только одного отца и все вершины являются потомками корневой вершины. Листом дерева называется вершина, не имеющая сыновей. Кроной дерева называется совокупность всех листьев. Высотой дерева называется наибольшая длина пути от коня к листу. Рекурсивное определение бинарного дерева: Дерево либо пусто, либо состоит из корня, а также левого и правого поддеревьев, которые в свою очередь так же являются бинарными деревьями. В прологе можно разработать предикаты для организации работы с деревьями.

DOMAINS

tree=empty;tr(i,tree,tree)

/* дерево либо пусто, либо

состоит из корня (целого числа),

левого и правого поддеревьев,

также являющихся деревьями */

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

tree_member(X,tr(X,_,_)):-!. /* X - является корнем

дерева */

tree_member(X,tr(_,L,_)):-

tree_member(X,L),!. /* X принадлежит

левому поддереву */

tree_member(X,tr(_,_,R)):-

tree_member(X,R). /* X принадлежит

правому поддереву */

Пример. Предикат, который будет заменять в дереве все вхождения одного значения на другое. У предиката будет четыре аргумента: три входных (значение, которое нужно заменять; значение, которым нужно заменять; исходное дерево), четвертым - выходным - аргументом будет дерево, полученное в результате замены всех вхождений первого значения на второе.

tree_replace(_,_,empty,empty). /* пустое дерево

остается пустым деревом*/

tree_replace(X,Y,tr(X,L,R),tr(Y,L1,R1)):-

/* корень содержит заменяемое

значение X*/

!,tree_replace(X,Y,L,L1),

/* L1 - результат замены

в дереве L всех вхождений X

на Y */

tree_replace(X,Y,R,R1).

/* R1 - результат замены

в дереве R всех вхождений X

на Y */

tree_replace(X,Y,tr(K,L,R),tr(K,L1,R1)):-

/* корень не содержит

заменяемое значение X */

tree_replace(X,Y,L,L1),

/* L1 - результат замены

в дереве L всех вхождений X

на Y */

tree_replace(X,Y,R,R1).

/* R1 - результат замены

в дереве R всех вхождений X

на Y */

Пример. Предикат, подсчитывающий общее количество вершин дерева. У него будет два параметра. Первый (входной) параметр - дерево, второй (выходной) - количество вершин в дереве.

tree_length (empty,0). /* В пустом дереве

нет вершин */

tree_length(tr(_,L,R),N):-

tree_length (L,N1),

/* N1 - число вершин

левого поддерева */

tree_length (R,N2),

/* N2 - число вершин

правого поддерева */

N=N1+N2+1. /* число вершин

исходного дерева

получается сложением

N1, N2 и единицы */

Пример. Разработаем предикат, подсчитывающий не общее количество вершин дерева, а только количество листьев, т.е. вершин, не имеющих сыновей. Предикат будет иметь два параметра. Входной - исходное дерево, выходной - количество листьев дерева, находящегося в первом параметре.

tree_leaves(empty,0). /* в пустом дереве

листьев нет */

tree_leaves(tr(_,empty,empty),1):-!.

/* в дереве с одним корнем -

один лист */

tree_leaves(tr(_,L,R),N):-

tree_leaves(L,N1),

/* N1 - количество листьев

в левом поддереве */

tree_leaves(R,N2),

/* N2 - количество листьев

в правом поддереве */

N=N1+N2.

Пример. Создадим предикат, находящий сумму чисел, расположенных в вершинах дерева. Он будет иметь два аргумента. Первый - исходный список, второй - сумма чисел, находящихся в вершинах дерева, расположенного в первом аргументе.

tree_sum (empty,0). /* В пустом дереве

вершин нет */

tree_sum(tr(X,L,R),N):-

tree_sum (L,N1),

/* N1 - сумма элементов

левого поддерева */

tree_sum (R,N2),

/* N2 - сумма элементов

правого поддерева */

N=N1+N2+X. /* складываем N1, N2

и корневое значение */

Пример. Создадим предикат, позволяющий вычислить высоту дерева. Напомним, что высота дерева - это наибольшая длина пути от корня дерева до его листа. Предикат будет иметь два параметра. Первый (входной) - дерево, второй (выходной) - высота дерева, помещенного в первый параметр.

tree_height(empty,0). /* Высота пустого

дерева равна нулю */

tree_height(tr(_,L,R),D):-

tree_height(L,D1),

/* D1 - высота левого

поддерева */

tree_height(R,D2),

/* D2 - высота правого

поддерева */

max(D1,D2,D_M),

/* D_M - максимум из высот

левого и правого поддеревьев */

D=D_M+1.

/* D - высота дерева получается

путем увеличения числа D_M

на единицу*/

Двоичные справочники – особый вид бинарных деревьев. В двоичном справочнике все значения входящие в левое поддерево меньше значения корня, в а значения в правом поддереве больше корня. Левое и правое поддеревья так же являются двоичными справочниками. Такие деревья упорядочены слева направо.

Предикат для проверки значения принадлежащего двоичному справочнику.

tree_member2(X,tr(X,_,_)):-!. /* X - корень

дерева */

tree_member2(X,tr(K,L,_)):-

X<K,!,

tree_member2(X,L).

/* X - принадлежит

левому поддереву */

tree_member2(X,tr(K,_,R)):-

X>K,!,

tree_member2(X,R).

/* X - принадлежит

правому поддереву */

Предикат добавляющий в двоичный справочник новое значение.

tree_insert(X,empty,tr(X,empty,empty)).

/* вставляем X в пустое дерево,

получаем дерево с X в корневой

вершине,пустыми левым и

правым поддеревьями */

tree_insert(X,tr(X,L,R),tr(X,L,R)):-!.

/* вставляем X в дерево

со значением X в корневой

вершине, оставляем исходное

дерево без изменений */

tree_insert(X,tr(K,L,R),tr(K,L1,R)):-

X<K,!,

tree_insert(X,L,L1).

/* вставляем X в дерево

с большим X элементом в

корневой вершине, значит,

нужно вставить X в левое

поддерево исходногодерева */

tree_insert(X,tr(K,L,R),tr(K,L,R1)):-

tree_insert(X,R,R1).

/* вставляем X в дерево

с меньшим X элементом

в корневой вершине, значит,

нужно вставить X в правое

поддерево исходного дерева */

Предикат генерирующий дерево, являющееся двоичным справочником и состоящее из заданного количества вершин в которых размещаются случайные целые числа.

tree_gen(0,empty):-!. /* ноль вершин

соответствует пустому дереву */

tree_gen (N,T):-

random(100,X),

/* X - случайное число

из промежутка [0,100) */

N1= N-1,

tree_gen (N1,T1),

/* T1 - дерево, имеющее

N-1 вершин */

tree_insert(X,T1,T). /* вставляем X

в дерево T1 */

Дерево не обязательно будет иметь столько вершин сколько указано в этом параметре, т.к. будут одни и те же числа. Если нужно получить содержащее ровно столько вершин, сколько указано, нужно модифицировать рассмотренный предикат, например, в случае когда вставляемое значение совпало с корневым генерировать новое случайное число для вставки в дерево.

Предикат удаляющий заданное значение из двоичного справочника. Опишем вспомогательный предикат удаляющий минимальный элемент двоичного справочника.

tree_del_min(tr(X,empty,R), R, X).

/* Если левое поддерево пусто,

то минимальный элемент - корень,

а дерево без минимального

элемента - это правое поддерево.*/

tree_del_min(tr(K,L,R), tr(K,L1,R), X):-

tree_del_min(L, L1, X).

/* Левое поддерево не пусто,

значит, оно содержит минимальное

значениевсего дерева,

которое нужно удалить */

tree_delete(X,tr(X,empty,R), R):-!.

/* X совпадает с корневым

значением исходного дерева,

левое поддерево пусто */

tree_delete (X,tr(X,L,empty), L):-!.

/* X совпадает с корневым

значением исходного дерева,

правое поддерево пусто */

tree_delete (X,tr(X,L,R), tr(Y,L,R1)):-

tree_del_min(R,R1, Y).

/* X совпадает с корневым

значением исходного

дерева, причем ни левое, ни

правое поддеревья не пусты */

tree_delete (X,tr(K,L,R), tr(K,L1,R)):-

X<K,!,

tree_delete (X,L,L1).

/* X меньше корневого значения

дерева */

tree_delete (X,tr(K,L,R), tr(K,L,R1)):-

tree_delete (X,R,R1).

/* X больше корневого значения

дерева */

Предикат, преобразующий произвольный список в двоичный справочник.

list_tree([],empty). /* Пустому списку

соответствует пустое дерево */

list_tree([H|T],Tr):-

list_tree(T,Tr1),

/* Tr1 - дерево, построенное

из элементов хвоста

исходного списка */

tree_insert(H,Tr1,Tr).

/* Tr - дерево, полученное

в результате вставки

головы списка в дерево Tr1 */

Предикат, преобразующий двоичный справочник в список.

tree_list(empty,[]). /* Пустому дереву

соответствует пустой список */

tree_list(tr(K,L,R),S):-

tree_list(L,T_L),

/* T_L - список,

построенный из элементов

левого поддерева */

tree_list(R,T_R),

/* T_L - список,

построенный из элементов

правого поддерева */

conc(T_L,[K|T_R],S).

/* S - список, полученный

соединением списков T_L

и [K|T_R] */

Сортировка списка.

sort_listT(L,L_S):-

list_tree(L,T),

/* T- двоичный справочник,

построенный из элементов

исходного списка L */

tree_list(T,L_S).

/* L_S - список, построенный из

элементов двоичного

справочника T */

Так как в двоичном справочнике все элементы различны, при переписывании списка в двоичный справочник и обратно повторяющиеся элементы будут из него удалены. Неизменным останется количество элементов списка, только если все его элементы были различны.

Дата добавления: 2014-01-07