Обходи дерева
Існує багато правил обходу дерев: прямий, зворотній, кінцевий і т.д.. Наприклад, розглянемо алгоритм прямого обходу.
1. Якщо дерево пусте, тоді нічого не робити.
2. В іншому випадку, обробити поточний вузел, потім обійти ліве піддерево обробленого вузла, а потім обійти праве піддерево обробленого вузла.
В Пролозі його можна реалізувати за допомогою двох фраз:
Traverse(empty).
traverse(tree(X,Y,Z):- do something with X, traverse(Y),
Traverse(Z).
Для того, щоб подивитись на нього в дії, розглянемо програму, зображену на мал.7.2, яка обходить дерево і друкує значення, що містяться в вузлах дерева.
Domains
treetype = tree(string, treetype, treetype);
Empty()
Predicates
Print_all_elements(treetype)
Clauses
Print_all_elements(empty).
print_all_elements(tree(X,Y,Z)):- write(X), nl,
Print_all_elements(Y),
Print_all_elements(Z).
goal: print_all_elements(tree("Cathy", tree("Michael",
tree("Charles", empty, empty),
tree("Hazel", empty, empty)),
tree("Melody", tree("Jim", empty,
empty), tree("Eleanor", empty,
Empty)))).
Мал.7.2.
Створення дерева.
Для багатьох задач виникає потреба створення структури даних типу дерева в пам'яті комп'ютера з подальшою її обробкою.
Створити один вузел дерева тривіально:
Create_tree(N, tree(N,empty,empty)).
Цей предикат можна інтерпретувати: "Якщо N є елементом даних, tree(N,empty,empty) є вузлом дерева,який містить цей елемент.
Процес побудови дерева трохи складніший. Розглянемо наступну фразу, яка містить предикат з трьома аргументами типу дерева. Він вставляє перше дерево в якості лівого піддерева другого дерева, використовуючи третє дерево як результуюче.
Insert_left(X, tree(A, _ , B), tree(A,X,B)).
Припустимо, наприклад, що ми хотіли б вставити
tree('Michael ' , empty, empty) в якості лівого піддерева
tree('Cathy', empty, empty). Це можна зробити, сформувавши запит:
goal : insert_left(tree('Michael',empty,empty),
tree('Cathy',empty,empty),
T)
де T зразу ж прийме значення tree('Cathy',
tree(Michael',empty,empty),
Empty).
Таким чином, ми поетапно можемо побудувати дерево. Програма, зображена на мал.7.3., демонструє використання запропонованого підходу для побудови дерева. На практиці, елементи, які розміщуються в вузлах дерева, майже завжди беруться з зовнішнього файлу.
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
* Прості процедури побудови дерева. *
* create_tree(A, B) вставляє A в поле даних дерева B *
* insert_left(A, B, C) вставляє A в якості лівого піддерева B, *
* отримуючи дерево C *
* insert_right(A, B, C) вставляє A в якості правого піддерева B, *
* отримуючи дерево С *
* *
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */