Представление бинарных деревьев
Одной из областей применения списков является представление множества объектов. Недостатком представления множества в виде списка является неэффективная процедура проверки принадлежности элемента множеству. Используемый для этой цели предикат member неэффективен при использовании больших списков. Для представления множеств могут использоваться различные древовидные структуры, которые обеспечивают более эффективную реализацию проверки принадлежности элемента множеству, в частности, в данном разделе для этой цели рассматриваются бинарные деревья. Представление бинарных деревьев основано на определении рекурсивной структуры данных, использующей функцию типа tree (Top, Left, Right) или tree (Left, Top, Right), где Top - вершина дерева, Left и Right - соответственно левое и правое поддерево. Пустое дерево обозначим термом nil. Объявить бинарное дерево можно следующим образом: Пример 45: domains treetype1=tree(symbol, treetype1, treetype1);nil treetype2=tree(treetype2, symbol, treetype2);nil Пример 46: Пусть дано дерево следующего вида: a b c d e
Такое дерево может быть задано следующим образом: 1. левое поддерево: tree (b, tree (d, nil, nil), tree (e, nil, nil)). 2. правое поддерево: tree (c, nil, nil). 3. все дерево: tree (a, tree (b, tree (d, nil, nil), tree (e, nil, nil)), tree (c, nil, nil)). Пример 47: написать программу проверки принадлежности вершины бинарному дереву. domains treetype = tree(symbol, treetype, treetype);nil() predicates in(symbol, treetype) clauses in(X, tree(X,_,_). in(X, tree(_,L,_):-in(X, L). in(X, tree(_,_,R):-in(X, R). goal in(d,tree(a, tree(b, tree(d, nil, nil), tree(e, nil, nil)), tree(c, nil, nil))). Поиск вершины в неупорядоченном дереве также неэффективен, как и поиск элемента в списке. Если ввести отношение упорядочения между элементами множества, то процедура поиска элемента становится гораздо эффективнее. Можно ввести отношение упорядочения слева направо непустого дерева tree(X, Left, Right) следующим образом: 1. Все узлы в левом поддереве Left меньше X. 2. Все узлы в правом поддереве Right больше X. 3. Оба поддерева также являются упорядоченными. Преимуществом упорядочивания является то, что для поиска любого узла в дереве достаточно провести поиск не более, чем в одном поддереве. В результате сравнения узла и корня дерева из рассмотрения исключается одно из поддеревьев. Пример 48: написать программу проверки принадлежности вершины упорядоченному слева направо бинарному дереву. domains treetype = tree(byte, treetype, treetype);nil() predicates in(byte, treetype) clauses in(X, tree(X,_,_). in(X, tree(Root,L,R):-Root>X,in(X, L). in(X, tree(Root,L,R):-Root<X,in(X, R). goal in(6,tree(4, tree(2, nil, tree(3, nil, nil)), tree(5,tree(1,nil,nil),nil)),tree(8,tree(7,nil,nil),tree(9,nil,tree(10,nil,nil)))). Пример 49: написать программу печати вершин бинарного дерева, начиная от корневой и следуя правилу левого обхода дерева. domains treetype = tree(symbol, treetype, treetype);nil() predicates print_all_elements(treetype) clauses print_all_elements(nil). print_all_elements(tree(X, Y, Z)) :- write(X), nl, print_all_elements(Y), print_all_elements(Z). goal print_all_elements(tree(a, tree(b, tree(d, nil, nil), tree(e, nil, nil)), tree(c, nil, nil))). Пример 50: написать программу проверки изоморфности двух бинарных деревьев. domains treetype = tree(symbol, treetype, treetype);nil predicates isotree (treetype, treetype) clauses isotree (T, T). isotree (tree (X, L1, R1), tree (X, L2, R2)):- isotree (L1, L2), isotree (R1, R2). isotree (tree (X, L1, R1), tree (X, L2, R2)):- isotree (L1, R2), isotree (L2, R1). Пример 51: написать предикаты создания бинарного дерева из одного узла и вставки одного дерева в качестве левого или правого поддерева в другое дерево. domains treetype = tree(symbol, treetype, treetype);nil predicates create_tree(symbol, tree) insert_left(tree, tree, tree) insert_rigth(tree, tree, tree) clauses create_tree(N, tree(N,nil,nil)). insert_left(X, tree(A,_,B), tree(A,X,B)). insert_rigth(X,tree(A,B,_), tree(A,B,X)). goal create_tree(a, T1)), insert_left(tree(b, nil, nil), tree(c, nil, nil), T2), insert_rigth(tree(d, nil, nil), tree(e, nil, nil), T3). В результате: T1=tree(a, nil, nil), T2=tree(c, tree(b, nil, nil), nil), T3=tree(d, nil, tree(e, nil, nil)).
Популярное: Модели организации как закрытой, открытой, частично открытой системы: Закрытая система имеет жесткие фиксированные границы, ее действия относительно независимы... Как распознать напряжение: Говоря о мышечном напряжении, мы в первую очередь имеем в виду мускулы, прикрепленные к костям ... Как построить свою речь (словесное оформление):
При подготовке публичного выступления перед оратором возникает вопрос, как лучше словесно оформить свою... ©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (393)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |