Page 46 - 4800

В обох випадках значення кореня і протилежного піддерева не змінюються.
Такому формулюванню відповідає процедура insert(), що має вигляд:
insert(end, X, tree(end, X, end)).
insert(tree(Left, Root, Right ), X, tree(LeftNew, Root, Right)) :- X < Root, insert(Left,
X, LeftNew).
insert(tree(Left, Root, Right), X, tree(Left, Root, RightNew)) :- X > Root, insert(Right,
X, RightNew).
Побудова бінарного дерева зі списку. Процедуру insert() можна
використовувати для побудови впорядкованого дерева зі списку. Процедура, що
забезпечує перетворення списку в упорядковане дерево, буде мати вигляд:
list_to_tree([], end).
list_to_tree([H | T], AllTree) :- list_to_tree(T, Tree), insert(Tree, H, AllTree).
Побудова відсортованого списку з дерева. Для рішення цієї задачі можна
скористатися упорядкованим бінарним деревом і об'єднанням списків.
Гранична умова: Порожнє бінарне дерево (end) приводить до порожнього списку
[].
Рекурсивна умова: Відсортований список для упорядкованого бінарного дерева
tree(Left, Root, Right), де Left має відсортований список L1, a Right має відсортований
список L2, отримується приєднанням [Root | L2] до L1.
tree_to_list(end, []).
tree_to_list(tree(Left, Root, Right), List) :- tree_to_list(Left, L1), tree_to_list(Right,
L2), append(L1, [Root | L2], List).
Розглянемо приклад використання цих процедур у Пролог-програмі, що працює
з базами даних різних структур і перетворення цих структур.
/* Програма 5_2 */
domains
worker = symbol
listworker = worker*
tree = tree(tree, worker, tree); end
predicates
db1(tree)
db2(listworker)
record(worker, tree )
append(listworker, listworker, listworker)
insert(tree, worker, tree)
list_to_tree(listworker, tree)
tree_to_list(tree, listworker)
goal1
goal2
goal3
goal4
goal5
goal6
goal7
goal8
clauses
goal1 :- db1(DB), write(DB).
goal2 :- db1(DB), record(R, DB), write(R), nl, fail.
goal3 :- db1(DB), write(„введіть елемент”), readln(E1), insert(DB, E1, DBnew),
write(DBnew).
goal4 :- db1(DB), write(„введіть елемент”), readln(E1), insert(DB, E1, DBnew),
record(R, DBnew), write(R), nl, fail.
goal5 :- db2(List), list_to_tree(List, Tree), write(Tree).
goal6 :- db2(List), list_to_tree(List, Tree), record(R, Tree), write(R), nl, fail.
goal7 :- db1(Tree), tree_to_list(Tree,List), write(List).
goal8 :- db2(List), write(List), nl, list_to_tree(List, Tree), write(Tree), nl,
tree_to_list(Tree, NewList), write(NewList), nl.
insert(end, X, tree(end, X, end)).
insert(tree(L, Root, R), X, tree(LNew, Root, R)) :- X < Root, insert(L, X, Lnew).

46