Бінарні дерева

Размещено на http://www.allbest.ru/

Лабораторна робота

Тема: Бінарні дерева

Мета: ознайомитися з елементами дерева, навчитися створювати структуру дерева та виводити його на екран.

1. Теоретичні відомості

бінарний дерево масив синтаксичний

Деревом називається орграф для якого:

1. Існує вузол, в якій не входить не однієї дуги. Цей вузол називається коренем.

2. В кожну вершину, окрім кореня, входить одна дуга.

З погляду уявлення про пам'ять важливо розрізняти два типи дерев: бінарні і багатогілкові.

В бінарному дереві з кожної вершини виходить не більше двох дуг. В багато гілковому дереві кількість дуг може бути довільною.

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

Рис. 1. ? Бінарне дерево

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

Рис. 2. ? Повне і неповне бінарні дерева

Рис. 3. ? Строго і не строго бінарні дерева

Бінарні дерева достатньо просто можуть бути представлений у вигляді списків або масивів. Облікове представлення бінарних дерев засновано на елементах, відповідних вузлам дерева. Кожний елемент має поле даних і два поля покажчиків. Один покажчик використовується для скріплення елемента з правим нащадком, а інший з лівим. Листя має порожні покажчики нащадків. При такому способі представлення дерева обов'язково слід зберігати покажчик на вузол, що є коренем дерева.

Можна помітити, що такий спосіб уявлення має схожість з простими лінійними списками. І ця схожість не випадкова. Насправді розглянутий спосіб представлення бінарного дерева є різновидом мультисписку, утвореного комбінацією безлічі лінійних списків. Кожний лінійний список об'єднує вузли, що входять в шлях від кореня дерева до одного з листя.

Рис. 4. ? Представлення бінарного дерева у вигляді спискової

структури

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

Рис. 5. ? Представлення бінарного дерева у вигляді масиву

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

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

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

адреса = 2k-1+i-1

де k ? номер рівня вершини,

i ? номер на рівні k в повному бінарному дереві.

Адреса кореня буде рівна одиниці. Для будь-якої вершини можна обчислити адреси лівого і правого нащадків:

адреса_L = 2к+2(i-1)

адреса_R = 2к+2(i-1)+1

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

У ряді алгоритмів обробки дерев використовується так зване проходження дерева. Під проходженням бінарного дерева розуміють певний порядок обходу всіх вершин дерева. Розрізняють декілька методів проходження.

Прямий порядок проходження бінарного дерева можна визначити таким чином:

· потрапити в корінь

· пройти в прямому порядку ліве піддерево

· пройти в прямому порядку праве піддерево

Рис. 6. ? Прямий порядок проходження бінарного дерева

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

· пройти в зворотному порядку ліве піддерево

· пройти в зворотному порядку праве піддерево

· потрапити в корінь

Рис. 7. ? Зворотний порядок проходження бінарного дерева

Визначимо ще один порядок проходження бінарного дерева, званий симетричним.

· пройти в симетричному порядку ліве піддерево

· потрапити в корінь

· пройти в симетричному порядку праве піддерево

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

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

Рис. 8. ? Представлення симетрично прошитого бінарного дерева у вигляді масивів

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

2. Хід роботи

1. Опрацюйте теоретичний матеріал.

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

Задача. Побудувати абстрактне синтаксичне дерево, кожна з вершин якого відображає операцію (+,-,*,/), кожний лист - значення числа. Підрахувати результат арифметичних операцій.

3. Програму записати у зошит. Різними кольорами виділіть у коді фрагменти, що відповідають за створення елементів дерева та його виведення на екран.

4. Програму протестуйте для виразу: 3+2*(4+7)-11.

Виведене на екран дерево відтворіть у зошиті.

5. Дайте відповіді на контрольні запитання

Текст програми:

program lab7_2;

uses crt;

type maintree=^tree; {покажчик на структуру "дерево"}

tree=record

a:real; {елемент дерева}

left:maintree; {покажчик на ліву гілку дерева}

right:maintree; {покажчик на праву гілку дерева }

end;

charset=set of char; {множина символів}

var sym:char; {визначення кінця вводу}

s:charset; {множина арифметичних операцій}

l,k,p:maintree; {покажчики на елементи дерева }

result,i,j,n:intege r; {робочі змінні}

m:real; {розрахунок виразу}

str:string; {рядок вхідних даних}

ms:array [1..10] of integer; {масив значень листків дерева}

mc:array [1..10] of char; {масив вершин}

{- формування масивів вузлових та термінальних вершин дерева -}

procedure form_array;

begin

repeat

readln(str); {ввід значень елементів дерева}

for i:=1 to length(str) do {аналіз рядка даних}

begin

if str[i] in s then {якщо елементом рядка є арифметична операція}

begin

n:=n+1; {лічильник рівнів дерева}

mc[n]:=str[i]; {формування значень вузлів дерева}

end

else {якщо елемент рядка не операція}

begin

j:=j+1; {лічильник термінальних вершин-листків}

val(str[i],ms[j],result); {перетворення символу в число, занесення до масиву чисел}

end;

end;

sym:=readkey; {ввід ознаки кінця вводу даних}

until sym='n'; { кінець вводу}

end;

{--------------відображення вхідного дерева-------------------- }

procedure enter_tree;

begin

gotoxy(12,20-2*n-1); write('Input tree :');

gotoxy(20,20); write(ms[2],' ',ms[1]); {термінальні вершини}

gotoxy(20,19); write(' / \ ');

for i:=1 to n-1 do {проміжні вершини дерева}

begin

gotoxy(20-i,20-2*i); write(ms[i+2],' ',mc[i]);

gotoxy(20-i,19-2*i); write(' / \');

end;

gotoxy(20-n+2,20-2*n); write(mc[n]);

end;

{---- виконання арифметичних дій, що задані у вузлах дерева ----}

procedure solution;

begin

new(l); {виділення пам'яті для правого листка дерева}

l^.a:=ms[1]; {значення листка - перший елемент масиву}

l^.left:=nil; {покажчики на лівий та правий листки порожні}

l^.right:=nil;

for i:=1 to n do {перебір вершин та аналіз дій}

begin

case mc[i] of {вибір та виконання операцій відповідно до вузлових вершин дерева}

'+': m:=l^.a+ms[i+1]; {якщо операція +, то знайти суму двох елементів,}

'-': m:=l^.a-ms[i+1]; {що знаходяться на термінальних вершинах одного рівня}

'*': m:=l^.a*ms[i+1];

'/': m:=l^.a/ms[i+1];

end;

new(k); {виділення пам'яті для кожного лівого листка дерева}

k^.a:=ms[i+1]; {визначення значення лівого листка}

k^.left:=nil; {покажчики порожні}

k^.right:=nil;

p:=l; {покажчик на поточний правий лист}

new(l); {пам'ять для кожної нової вершини}

l^.a:=m; {значення вершини-результат виконання операцій}

l^.right:=p; {правий покажчик на поточну вершину}

l^.left:=k; {лівий покажчик на поточну ліву вершину}

end;

end;

{---------- відображення дерева результатів обчислення ----------}

procedure print_tree;

begin

p:=l; {покажчик на корінь дерева}

gotoxy(35,20-2*n-1); write('Building tree :');

gotoxy(42,20-2*n); write(l^.a:3:1); {вивід значення кореня дерева}

for i:=1 to n do {вивід n-рівневого дерева}

begin

gotoxy(40+2*i,20-2*n+2*i);

l:=l^.left; {переміщення покажчика ліворуч від поточної вершини}

write(l^.a:3:1); {вивід значення лівої вершини}

gotoxy(45+2*i,20-2*n+2*i);

p:=p^.right; {переміщення покажчика праворуч від поточної вершини}

write(p^.a:1:1); {вивід значення правої вершини}

gotoxy(40+2*i,20-2*n+2*i-1); write(' / \');

l:=p; {перепризначення покажчика}

end; gotoxy(1,23);

end;

{--------------------------- головна програма ---------------------------}

begin clrscr;

n:=0; {початкове значення рівнів дерева}

j:=0; {початкове значення листків дерева}

s:=['+','-','*','/']; {множина вузлів дерева}

writeln(' введіть арифметичний вираз та натисніть клавішу n для закінчення:');

form_array; {формування масивів вузлових та термінальних вершин дерева}

enter_tree; {вивід вхідного дерева}

solution; {виконання арифметичних дій,що задані в вузлах дерева}

print_tree; {вивід дерева результатів}

readkey;

end.

3. Контрольні запитання

1. Дайте означення структури дерево.

2. Назвіть основні елементи бінарного дерева.

3. Які види дерев ви знаєте, зобразіть їх схематичний малюнок.

4. Відтворіть всі методу обходу дерев.

5. У якому вигляді можна представити дерево. Проілюструйте дані представлення.

Размещено на Allbest.ru