Лабораторна робота №4

Структура даних типу дерева

Тема: Структура даних типу дерева.

Мета: Одержати практичні навички роботи зі структурою даних типу дерева в середовищі Strawberry Prolog.

Теоретичні відомості.

Серед структур даних типу дерева можна виділити спеціальний клас найбільш вживаних дерев - бінарні дерева. Можна дати наступне рекурсивне визначення бінарного дерева:

1.Пусте дерево – бінарне дерево.

2.Кожний вузол бінарного дерева має не більше одного лівого бінарного піддерева і не більше одного правого бінарного піддерева.

Таку структуру даних в Пролозі можна визначити за допомогою двох предикатів:

treetype = tree(string,treetype,treetype) та empty

Останній використовується для позначення пустого дерева.

Обходи дерева.

Існує багато правил обходу дерев: прямий, зворотній, кінцевий і т.д.. Наприклад, розглянемо алгоритм прямого обходу.

Якщо дерево пусте, тоді нічого не робити.

В іншому випадку, обробити поточний вузел, потім обійти ліве піддерево обробленого вузла, а потім обійти праве піддерево обробленого вузла.

В Пролозі його можна реалізувати за допомогою двох фраз:

traverse(empty).

traverse(tree(X,Y,Z):-do something with X, traverse(Y), traverse(Z).

Хід роботи

Завдання:

Варіант 10: Написати програму в середовищі Strawberry Prolog, яка поетапно будує дерево виду:

, де х1...х7 строки введені із клавіатури. Результат вивести на екран.

Лістинг програми:

%simple binary tree building program

%lab_4

%made by KL

create_tree(A, tree(A, empty, empty)).

insert_left(X, tree(A, _, B), tree(A, X, B)).

insert_right(X, tree(A, B,_), tree(A, B, X)).

?-

read(X1),read(X2),read(X3),read(X4),read(X5),read(X6),read(X7),

create_tree(X1,X1_t),create_tree(X2,X2_t),create_tree(X3,X3_t),

create_tree(X4,X4_t),create_tree(X5,X5_t),create_tree(X6,X6_t),

create_tree(X7,X7_t),

insert_left(X6_t,X4_t,X4_tl),insert_right(X7_t,X4_tl,X4_tf),

insert_left(X4_tf,X3_t,X3_tl),insert_right(X5_t,X3_tl,X3_tf),

insert_left(X2_t,X1_t,X1_tl),insert_right(X3_tf,X1_tl,X1_tf),

write("The structure of the tree is:"),nl,write(X1_tf),nl.

Результати:

The structure of the tree is:

tree(1,tree(2,empty,empty),tree(3,tree(4,tree(6,empty,empty),tree(7,empty,empty)),tree(5,empty,empty)))

Yes.

Висновок: на лабораторній роботі я одержав практичні навички роботи зі структурою даних типу дерева в середовищі Strawberry Prolog. Створив програму, яка будує дерево з семи вершин, значення яких вводяться з клавіатури.