readchar(_).

action(7, _, end):- exit.

create_Tree(Tree, NewTree):-

readchar(C),

C <> 0'#' , !,

write(C, " "),

insert(C, Tree, TempTree),

create_Tree(TempTree,NewTree).

create_Tree(Tree, Tree).

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

insert(New,

tree(Element, Left, Right),

tree(Element, NewLeft, Right)):-

New < Element, !,

insert(New, Left, NewLeft).

insert(New, tree(Element, Left, Right),

tree(Element, Left, NewRight)):-

insert(New, Right, NewRight).

write_Tree(end).

write_Tree(tree(Item, Left, Right)):-

write_Tree(Left),

write(Item, " "),

write_Tree(Right).

repeat.

repeat:-repeat.

7.1.Написати програму, яка б визначала кількість вершин-листків в бінарному дереві.

7.2.Написати програму, яка створює копію бінарного дерева.

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

а)висота пустого дерева Т рівна H(T)=0;

б)висота непустого бінарного дерева Т з коренем к і піддеревами Т1 і Т2 дорівнює H(T)=1+max(H(T1), H(T2)).

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

8. РОБОТА З СПИСКАМИ В ПРОЛОЗІ.

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

[1,2,3], [dog, cut, canary]

Як ми вже зазначали, списки описуються за допомогою спеціального знаку (*) “зірочка”. Він добавляється до кінця попередньо визначеної області. Наприклад,

domains

integerlist = integer*

Eлemeнтом списку можуть бути любі дані, навіть інші списки. Всі елементи списку повинні належати до однієї області. Декларація областей для елементів повинна мати таку форму:

domains

elementlist = elements*

elements = integer

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

domains

elementlist = elements*

elements = i(integer); r(real); s(symbol)

8.1.Рекурсивна сутність списку.

Список - це рекурсивна структура, яка складається з голови та хвоста. Головою називають перший елемент списку, а хвіст - це всі інші елементи. Хвіст списку завжди буде списком, а голова - один елемент. Зазначимо, що пустий список не можна розбити на голову і хвіст.

Концептуально списки мають структуру дерева. Наприклад, список [a, b, c, d] можна представити в наступному вигляді:

list

/ \

a list

/ \

b list

/ \

c list

/ \

d []

А одноелементний список, [a] має вигляд:

list

/ \

a []

8.2.Обробка списків.

Пролог дає можливість явно створювати голову і хвіст списку. Замість відокремлення елементів комами, ви можете розділити голову і хвіст знаком (|).

Наприклад, список [a, b, c] дорівнює списку [a | [b, c]] , який в свою чергу рівний списку [a|[b|[c|[]]]].

Розподільниками можна також комбінувати. Так список [a, b, c, d] можна задати у вигляді [a, b|[c, d]].

Для обробки списків найбільш підходять рекурсивні алгоритми. Обробка списку складається з рекурсивного зсуву і обробки голови списку до тих пір, поки список не стане пустим. Алгоритм такого типу, традиційно має дві фрази. Перша з них говорить, що потрібно робити з списком, а друга - що робити з пустим списком.

8.2.1.Друк списків.

Список можна роздрукувати так:

domains

list = integer* /* або ж інший тип, який ви бажаєте використовувати */

predicates

write_a_list(list)

clauses

write_a_list([]). /* якщо список пустий, тоді нічого не потрібно робити

write_a_list([H|T]) :- /* Виділяємо голову списку Н і хвіст Т,

потім роздруковуєм Н і рекурсивно обробляємо Т */

write(H), nl,

write_a_list(T).

Якщо ми задамо запит типу:

goal : write_a_list([1, 2, 3]).

Тоді список [1,2,3] буде розбито на голову Н=1 і хвіст Т = [2,3]. Предикатом write(H) роздрукується голова і рекурсивно буде оброблятись предикатом write_a_list(T) хвіст [2,3]. Процес закінчиться, коли хвіст стане пустим.

8.2.2.Підрахунок кількості елементів.

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

Довжина пустого списку [ ] рівна 0.

Довжина непустого списку рівна 1 плюс довжина його хвосту.

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

domains

list = integer*

predicates

length_of(list, integer)

clauses

length_of([], 0).

length_of([_|T], L) :- length_of(T, TailLength),

L = TailLength + 1.

Поглянемо спочатку на другу фразу. Так, length_of [_ ,|T] порівнює любий непустий список, прив`язуючи T до хвосту списка. Значення голови не суттєво, ЕОМ буде її рахувати як один елемент.

Так ціль

goal: length_of([1,2,3], L) ,

використовуючи другу фразу, зв'яже з T значення [2,3]. Наступний крок - обчислити довжину T. Коли це зроблено, не важливо як, тоді TailLength отримає значення 2, і ЭВМ потім зможе добавити до неї 1 та прив'язати L до 3.

Для того, щоб визначити довжину [2,3] рекурсивно викличеться length_of([2,3], TailLength. Ця ціль зрівнює другу фразу, прив'язуючи - [3] до T . Тепер виникає задача, як знайти довжину [3], яка дорівнює 1, а потім добавить 1, щоб отримати довжину [2,3], яка буде 2. І так далі і тому подібно. Тому length_of знов викличе себе рекурсивно, щоб отримати довжину списку [3]. Хвіст для [3] рівний [ ], тому T зв'яжеться з [], і задача зараз полягає в тому , щоб знайти довжину [], потім додати до неї 1, і знайти довжину [3]. На цей раз це зробити легко. Ціль length_of([], Tail Length зрівнюючи першу фразу, зв'яже TailLength з 0. Тепер ЭОМ може додати 1 до неї, отримуючи довжину списку [3] і повернутися до фрази виклику. Яка , в свою чергу , прибавить знову 1 , отримуючи довжину [2,3] і повернеться до фрази, яка викликала її; ця початкова фраза прибавить знову 1 , знаходячи довжину списку [1,2,3].

Малюнок 8.1 показує дійсний процес обчислення довжини списку. Ми використали тут різні змінні, щоб підкреслити той факт, що змінні з одинаковими