Головна Головна -> Інше українською -> Інформатика, комп'ютери, програмування -> Структура даних типу дерева

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

Назва:
Структура даних типу дерева
Тип:
Інше
Мова:
Українська
Розмiр:
1,34 KB
Завантажень:
271
Оцінка:
 
поточна оцінка 5.0


Скачати цю роботу безкоштовно
Лабораторна робота №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. Створив програму, яка будує дерево з семи вершин, значення яких вводяться з клавіатури.

Завантажити цю роботу безкоштовно



Інше на тему: Структура даних типу дерева

BR.com.ua © 1999-2017 | Реклама на сайті | Умови використання | Зворотній зв'язок