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.Друк списків.

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

Наши рекомендации