Логическое программирование на языке Visual Prolog. Солдатова О.П - 53 стр.

UptoLike

ВУЗ: 

СГАУ | Самара

Составители: 

Рубрика: 

53
Пример 62: написать программу проверки принадлежности вершины
бинарному дереву.
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. Оба поддерева также являются упорядоченными.
Преимуществом упорядочивания является то, что для поиска любого
узла в дереве достаточно провести поиск не более, чем в одном поддереве. В
результате сравнения узла и корня дерева
из рассмотрения исключается одно
из поддеревьев.
Пример 63: написать программу проверки принадлежности вершины
упорядоченному слева направо бинарному дереву.
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)
))).
Пример 64: написать программу печати вершин бинарного дерева,
начиная от корневой и следуя правилу левого обхода дерева.
domains
treetype = tree(symbol, treetype, treetype);nil()

Страницы