КАТЕГОРИИ: Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748) |
Деревья. Деревами называется граф, у которого одна вершина корневая, а остальные вершины имеют только одного отца и все вершины являются потомками корневой вершины
Деревами называется граф, у которого одна вершина корневая, а остальные вершины имеют только одного отца и все вершины являются потомками корневой вершины. Листом дерева называется вершина, не имеющая сыновей. Кроной дерева называется совокупность всех листьев. Высотой дерева называется наибольшая длина пути от коня к листу. Рекурсивное определение бинарного дерева: Дерево либо пусто, либо состоит из корня, а также левого и правого поддеревьев, которые в свою очередь так же являются бинарными деревьями. В прологе можно разработать предикаты для организации работы с деревьями. 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; Просмотров: 739; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |