2.3. Приклад 1 роботи з деревами (рекурсивний обхід і виведення значень вузлів існуючого дерева)

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

У наведеному далі лістингу 11_1 представлено приклад Пролог-програми, що здійснює рекурсивний обхід вузлів дерева, з виведенням на екран комп`ютеру значень усіх коренів дерева.

Спосіб розв'язування даної задачі описано нижче.

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

Якщо дерево є непорожнім, то необхідно виконати наступні дії:

– розділити дерево на три частини (корінь, ліве піддерево та праве піддерево);

– виконати виведення на екран комп`ютеру того значення, що знаходиться в корені дерева;

– обробити ліве та праве піддерева.

Кожна з умов в описі задачі відповідає реченню в Пролог-програмі.

Прокоментуємо основні правила Пролог-програми.

Правило "Дерево є порожнім, а тому жодні подальші дії не виконуються" набуде наступного вигляду: print_tree (nil):- !.

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

print_tree (tree(Root, Left, Right)):-

write(Root), nl,

print_tree (Left),

print_tree (Right).

Результат роботи програми має наступний вигляд:

4

2

1

3

5

% Sheet 11_1. Primer 1 on the recursive creating and processing for tree

DOMAINS

treetype = tree (integer, treetype, treetype); nil ()

PREDICATES

print_tree (treetype)

CLAUSES

print_tree (nil):- !.

print_tree (tree(Root, Left, Right)):-

write(Root), nl,

print_tree (Left),

print_tree (Right).

GOAL

print_tree (tree (4, tree (2, tree (1, nil, nil), tree (3, nil, nil)), tree (5, nil, nil))).

2.4. Приклад 2 роботи з деревами (рекурсивна побудова нового впорядкованого дерева, з виведенням опису його структури та значень вузлів)

Деревовидну структуру даних можна створити програмним шляхом.

У наведеному далі лістингу 11_2 представлено приклад Пролог-програми, що здійснює наступні дії:

– рекурсивну побудову нового впорядкованого дерева, починаючи з порожнього дерева (застосовується метод додавання нових вузлів до поточного дерева зі збереженням впорядкованості даного дерева);

– виведення на екран комп`ютеру повного опису дерева (структури дерева та значень, розташованих у вузлах дерева).

Можливі наступні три варіанти додавання нових вузлів у процесі побудови впорядкованого дерева:

1) додавання нового вузла до порожнього дерева;

2) додавання нового вузла до непорожнього дерева в тому випадку, коли значення в новому вузлі є меншим за значення в корені дерева (новий вузол у даному випадку потрібно буде додавати до лівого піддерева);

3) додавання нового вузла до непорожнього дерева в тому випадку, коли значення в новому вузлі є більшим за значення в корені дерева (новий вузол у даному випадку потрібно буде додавати до правого піддерева).

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

Реалізуємо зазначений підхід за допомогою наступного правила:

insert (New, nil, tree (New, nil, nil)).

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

1) порівнюють значення вузла, який потрібно додати до дерева, зі значенням кореня поточного дерева;

2) у тому разі, якщо значення вузла, який потрібно додати, виявиться меншим за значення в корені дерева – додають новий вузол до поточного лівого піддерева (з отриманням таким чином нового лівого піддерева).

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

Реалізуємо вказаний підхід за допомогою наступного рекурсивного правила:

insert (New, tree (Root, Left, Right), tree (Root, NewLeft, Right)):-

New < Root, !,

insert (New, Left, NewLeft).

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

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

Очевидно, що в даному випадку ліве піддерево потрібно залишити без жодних змін.

Реалізуємо вказаний підхід за допомогою наступного рекурсивного правила:

insert (New, tree (Root, Left, Right), tree (Root, Left, NewRight)):-

insert (New, Right, NewRight).

Використаємо наведені вище речення в Пролог-програмі, що покроково будує дерево зі збереженням його впорядкованості (лістинг 11_2).

Процес і результати роботи Пролог-програми представлено нижче за текстом.

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

– після введення кожного значення, натискається клавіша Enter;

– для завершення процесу введення, на клавіатурі набирається будь-який символ, який не є цілим числом, і натискається клавіша Enter.

Наприклад, для більшої наочності, можна ввести ряд значень 1, 2, 3, 4, 5 і завершити введення літерою a:

1 Enter

2 Enter

3 Enter

4 Enter

5 Enter

a Enter

Згідно з введеними даними, Пролог-програмою буде здійснено рекурсивну побудову впорядкованого дерева та виведення на екран комп`ютеру опису його структури та значень вузлів у наступному форматі:

tree(1, nil, tree(2, nil, tree(3, nil, tree(4, nil, tree(5, nil,nil)))))

% Sheet 11_2. Primer 2 on the recursive creating and processing for tree

DOMAINS

treetype = tree (integer, treetype, treetype); nil ()

PREDICATES

create (treetype, treetype)

insert (integer, treetype, treetype)

CLAUSES

create (Tree, NewTree):-

readint (New), !,

insert (New, Tree, TmpTree),

create (TmpTree, NewTree).

create (Tree, Tree).

insert (New, nil, tree (New, nil, nil)):- !.

insert (New, tree (Root, Left, Right), tree (Root, NewLeft, Right)):-

New<Root, !,

insert (New, Left, NewLeft).

insert (New, tree (Root, Left, Right), tree (Root, Left, NewRight)):-

insert (New, Right, NewRight).

GOAL

create (nil, Tree),

write (Tree).