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

В якості вершини дерева завжди розміщується перший по-порядку елемент. Кожен новий елемент дерева розміщується у ньому так, щоб він опинився лівіше від поточної вершини, якщо він менший від неї; і правіше, якщо він більший від неї.

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

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

USES CRT;

TYPE

bintree=^el_bintree;

el_bintree=record

left,right:bintree;

inf:integer;

END;

Дії, які можна проводити з бінарними деревами:

Формування.

Перегляд.

Пошук.

Встановлення ширини та висоти дерева.

Встановлення кількості вузлових вершин, листків та напівисячих вершин.

Доповнення новим елементом (операція вставки перед (чи після) не має змісту, оскільки будь-який елемент у дереві розміщується в строго визначеному йому місці).

Вилучення елемента із дерева.

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

PROCEDURE ZAPUS (var p:bintree;a:integer);

BEGIN

new(p);

p^.left:=nil;

p^.right:=nil;

p^.inf:=a;

END;

PROCEDURE ROZM(var q:bintree;a:integer);

BEGIN

if q^.inf<a then

Begin

if q^.left<>nil then ROZM (q^.left,a)

else ZAPUS(q^.left,a);

end;

if q^.inf>a then

Begin

if q^.right<>nil then ROZM(q^.right,a)

else ZAPUS(q^.right,a);

end;

END;

PROCEDURE INPUT;

BEGIN

top:=nil;

writeln('введіть кількість елементів');

readln(n);

for i:=1 to n do

Begin

writeln('введіть елемент:');

readln(k);

if top=nil then ZAPUS(top,k)

else ROZM(top,k);

end;

END;

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

Здійснюватиметься рух по дереву до крайнього лівого елемента (найменшого).

Це значення друкується.

Робиться один крок вправо і послідовність 1-3 повторюється відносно нової поточної вершини.

Програмна реалізація алгоритму друку має вигляд процедури:

PROCEDURE OUTPUT (p:bintree);

BEGIN

if p^.left<>nil then OUTPUT(p^.left);

write(p^.inf,' ');

if p^.right<>nil then OUTPUT(p^.right);

END;

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

PROCEDURE FIND (p:bintree; x:integer);

BEGIN

inc(i);

if p^.right<>nil then FIND(p^.right,x);

if p^.inf=x then

Begin

write('є під номером(ами) ');

Str(i,d);

s:=s+d;

end;

if p^.left<>nil then FIND(p^.left,x);

if (p=top) and (s='') then writeln('елемент не знайдено');

END;

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

PROCEDURE MOVE_RIGHT(p:bintree);

BEGIN

if p^.right<> nil then

Begin

k:=k+1;

MOVE_RIGHT(p^.right)

end;

END;

PROCEDURE MOVE_LEFT(p:bintree);

BEGIN

if p^.left<> nil then

Begin

k:=k+1;

MOVE_LEFT(p^.left)

end;

END;

В основній програмі це буде мати вигляд:

n:=0;

k:=0;

MOVE_RIGHT(top);

MOVE_LEFT(top);

writeln('ширина:',n+k+1);

Процедура визначення висоти бінарного дерева буде мати вигляд:

PROCEDURE HIGHT(p:bintree;k:integer);

BEGIN

if p^.left<>nil then HIGHT(p^.left, k+1);

if k>h then h:=k;

if p^.right<>nil then HIGHT(p^.right,k+1)

END;

Для встановлення кількості висячих вершин використовують таку процедуру:

PROCEDURE LUSTOK(p:bintree;var l:word);

Begin

if (p^.left=nil) and (p^.right=nil) then inc(l);

if p^.left<>nil then LUSTOK(p^.left,l);

if p^.right<>nil then LUSTOK(p^.right,l);

end;

Доповнення новим елементом проводиться так само як формування дерева.

Складність видалення пов’язана із тим, що приходиться аналізувати декілька можливих ситуацій:

а). Видалення висячої вершини найбільш проста. Вона передбачає встановлення у nil вказівника на елемент, що видаляється, для цього потрібно мати фіксований вказівник на попередній елемент.

Dispose(p^.right);

p^.right:=nil;

Dispose(p^.left);

p^.left:=nil;

б). Видалення напіввисячої вершини. При цьому всі елементи, що знаходяться нижче елемента, що видаляється підтягуються на один рівень вверх.

Тема: Модульний принцип організації програм.

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

В ранніх компіляторах мови Turbo Pascal з'явилася перша можливість розділення програм на окремі модулі, при цьому в модулях зосереджувалися окремі компоненти мови, що пов'язувалися спільними властивостями.

Ці модулі окремо компілювалися і були доступними для всіх програм; це були свого роду бібліотеки інструментів мови програмування.

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

З розвитком мов програмування з'явилися бібліотеки динамічної компоновки.

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

Результатами компіляції є файл, компоненти якого готові до виконання. Такі файли мають розширення *.tpu (Turbo Pascal Unit). Всі модулі, що використовуються однією програмою або іншими модулями повинні бути оголошені

USES <ім'я модуля>;

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

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

Заголовок.

UNIT <ім'я модуля>;

На відмінну від програм, заголовок модуля є обов’язковим. Ім'я модуля повинно співпадати з іменем відповідного *.pas-файлу, що містить текст модуля (8 букв).

Інтерфейс на частина.

ІNTERFACE

TYPE

compl=record

Re,im:real

END;

PROCEDURE SUMA (a,b:compl; var d:compl);

PROCEDURE RIZNUTSYA (a,b:compl; var d:compl);

PROCEDURE DOBYTOK (a,b:compl; var d:compl);

PROCEDURE CHASTKA (a,b:compl; var d:compl);

FUNCTION MODYL (a:compl):real;

FUNCTION ARGYMENT (a:compl):real;

В розділі інтерфейс оголошуються всі компоненти модуля, структура яких і самі вони мають бути „видимими” зовнішнім програмам, що використовують цей модуль.

В інтерфейсі можуть оголошуватися: uses- специфікація всіх модулів, що використовуються даним модулем; константи; типи; мітки; змінні; заголовки підпрограм. Всі перелічені компоненти будуть доступними, тобто „видимими” іншим програмам.

Підпрограми зовні модуля будуть видимі лише своїм інтерфейсом, причому описується, що це за підпрограма: процедура чи функція; ім'я, повний список формальних параметрів та тип результату для функції.

Такий спосіб оголошення підпрограм приховує внутрішню реалізацію відповідних підпрограм, а залишає доступним лише перелік параметрів та ім'я.

Розділ реалізації. В реалізації описуються всі компоненти мови, які мають бути невидимі зовні.

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

При описі реалізації підпрограм в цьому розділі може задаватися лише скорочений заголовок без списку формальних параметрів.

Implementation

PROCEDURE SUMA;

BEGIN

d.Re:=a.Re+b.Re;

d.Im:=a.Im+b.Im;

END;

PROCEDURE RIZNUTSYA;

BEGIN

d.Re:=a.Re-b.Re;

d.Im:=a.Im-b.Im;

END;

Розділ ініціалізації початкових значень змінних. Цей розділ є необов’язковим і містить оператори присвоєння змінним із розділу інтерфейс, якщо вони є деяких початкових значень, якщо вони відмінні від значень по-замовчуванню.