5.1 Методичні вказівки до самостійної роботи і виконання роботи

Дерева належать до рекурсивних структур даних (рис.5.1). Важливо, щоб кожна гілка дерева сама була деревом, тому структура рекурсивна.

Рисунок 5.1  Частина сімейного дерева

Дерева – як типи даних

Пролог дозволяє визначити рекурсивні типи, у яких вказівки створюються та обробляються автоматично. Наприклад, можна визначити дерево так:

domains

treetype = tree (string, treetype, treetype)

Ця декларація говорить про те, що дерево записується як функтор tree (дерево), аргументами якого є рядок і два інших дерева.

Але це не зовсім правильно, оскільки немає способу закінчити рекурсію. Насправді дерево не може поширюватися нескінченно. Деякі вузли не мають зв’язку з іншими деревами. У Пролозі нема доступу до указників. Рішення полягає в тому, щоб визначити два типи дерев – звичайне і вільне. Це досягається тим, що дерево може мати одне з двох описів tree (дерево) з трьома аргументами або empty (вільно) без аргументів.

domains

treetype = tree (string, treetype, treetype); empty

Зауважте, що назва tree (функтор у якого три аргументи) і empty (функтор без аргументів) створюються програмістом та жодному з них нема визначеного в Пролозі значення. З тим самим успіхом можна використовувати xxх і yyy.

Ось як дерево на рис. 5.1 буде описано в прологівській програмі:

tree ("Катя",

tree ("Мишко",

tree ("Вова", empty, empty),

tree ("Ліда", empty, empty)),

tree ("Люда",

tree ("Зіна", empty, empty),

tree ("Петрик", empty, empty)))

Для зручності читання програма має підрозділи. Але в Пролозі не потрібно такого підрозділу, і деревам, при нормальному записі, не потребуються підрозділи. Така ж структура буде складена іншим способом:

tree ("Катя",

tree ("Мишко",

tree ("Вова", empty, empty),

tree ("Ліда", empty, empty)),

tree ("Люда",

tree ("Зіна", empty, empty),

tree ("Петрик", empty, empty)))

Зауважте, що це не речення Прологу, а лише суцільна структура даних.

Обхід дерева

Однією з найбільш частих операцій з деревом є дослідження всіх вузлів та обробка їх деяким чином, або пошук деякого значення, або пошук всіх значень. Ці процедури відомі як обхід дерева. Основним алгоритмом є такий:

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

2. Інакше, обробити поточне значення, потім перейти на ліве піддерево, потім перейти на праве піддерево.

Як і саме дерево, алгоритм є рекурсивним: він обробляє ліве та праве під дерево так само, як і початкове дерево. У Пролозі він виражається двома реченнями: одне для вільного, а інше для заповненого дерева.

обхід (empty). /* нічого не робить */

обхід (tree (X, Y, Z)): 

робити будь-що з X,

обхід (X),

обхід (Z).

Рисунок 5.2 – Обхід дерева з рисунка 5.1 "спочатку вглиб"

Цей алгоритм відомий як пошук "спочатку вглиб", оскільки він спускається по кожній гілці вниз, наскільки можливо, перед тим як повернутися нагору для обходу іншої гілки (рис.5.2). Щоб розглянути алгоритм у дії, виконайте програму Lab5_1.PRO, яка обходить дерево та друкує всі елементи які вона зустрічає. Дерево показане на рисунках 5.1 і 5.2, Lab5_1.PRO роздрукує

Катя

Мишко

Вова

Ліда

Люда

Зіна

Петрик

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

/* Програма Lab5_1.PRO */

/* Обхід дерева "спочатку вглиб" і друк кожного елемента, що є на шляху. */

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 ("Катя",

tree ("Мишко",

tree ("Вова", empty, empty),

tree ("Ліда", empty, empty)),

tree ("Люда",

tree ("Зіна", empty, empty),

tree ("Петрик", empty, empty)))),nl,fail;true.

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

мати ("Катя", "Люда").

мати ("Катя", "Мишко").

батько ("Мишко", "Вова").

батько ("Мишко", "Ліда"). ...

Це було б краще, якщо дерево призначалося тільки для вираження родинних зв’язків між людьми. Але такий вигляд опису робить неможливим обробку всього дерева як одної, складної структури даних. Отже комплексні структури даних бувають дуже корисними, оскільки вони спрощують складні обчислення задачі.