Новини освіти і науки:

G+

Тлумачний словник
Авто
Автоматизація
Архітектура
Астрономія
Аудит
Біологія
Будівництво
Бухгалтерія
Винахідництво
Виробництво
Військова справа
Генетика
Географія
Геологія
Господарство
Держава
Дім
Екологія
Економетрика
Економіка
Електроніка
Журналістика та ЗМІ
Зв'язок
Іноземні мови
Інформатика
Історія
Комп'ютери
Креслення
Кулінарія
Культура
Лексикологія
Література
Логіка
Маркетинг
Математика
Машинобудування
Медицина
Менеджмент
Метали і Зварювання
Механіка
Мистецтво
Музика
Населення
Освіта
Охорона безпеки життя
Охорона Праці
Педагогіка
Політика
Право
Програмування
Промисловість
Психологія
Радіо
Регилия
Соціологія
Спорт
Стандартизація
Технології
Торгівля
Туризм
Фізика
Фізіологія
Філософія
Фінанси
Хімія
Юриспунденкция

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

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

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

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

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;

<== попередня сторінка	\|	наступна сторінка ==>
Dispose(p)	\|	Щоб визначити ширину дерева достатньо здійснити рекурсивний рух вліво і вправо до кінця відносно вершини із підрахунком кількості кроків, а потім додати.

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.005 сек.