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.Друк списків.
Список можна роздрукувати так: