2.8. Дерева

2.8.1. Теоретичні вказівки

Дерево - це скінчена множина вузлів з одним виділеним вузлом, що називається коренем, а інші вузли розділені на m множин, що не перетинаються і кожна з яких становить піддерево. Для кожного вузла k існує послідовність вузлів k₀,k₁,.,k_n, що утворює гілку довжини n. Вузли , що не мають піддерев , складають листя дерева. Ступінь вузла К - це кількість його піддерев. Дерево проходять в прямому порядку, якщо спочатку відвідують корінь, а потім всі його піддерева в відповідності з їхнім упорядкуванням (переліком номерів вершин, що задається користувачем). Дерево проходять в оберненому порядку, якщо спочатку проходять його піддерева в відповідності з їхнім упорядкуванням, а потім відвідують корінь.

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

Бінарне дерево - це упорядковане дерево ступеня 2, що має такі властивості: дерево може бути порожнім, будь-який вузол може мати інший (правий) вузол за відсутності першого (лівого). Бінарні дерева можна проходити в прямому або в оберненому порядках. Можливий симетричний порядок проходу: проходять ліве піддерево, корінь, праве піддерево. Для перетворення звичайного дерева в бінарне необхідно залишити зв'язки від батьків до їх перших синів (це ліві зв'язки бінарного дерева), додати нові зв'язки між синами батька в відповідності з їх упорядкуванням (праві зв'язки дерева).

2.8.2. Приклад програми

Умова задачі

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

Алгоритм

1. Формування масивів вузлових та термінальних вершин дерева. Повторювати дії, поки не натиснута клавіша 'n' :

1.1.1. Ввід значень елементів дерева;

1.1.2. Якщо елемент рядка - це арифметична операція, то формувати значення вузлів дерева;

1.1.3. Якщо елемент рядка - це число, то занести його до масиву;

1.1.4. Ввід ознаки кінця вводу даних.

2. Вивід вхідного дерева:

2.1. Вивід термінальних вершин;

2.2. Циклічний вивід проміжних вершин.

3. Виконання арифметичних дій, що задані в вузлах дерева:

3.1. Виділення пам'яті для правого листка дерева, визначення значення листка;

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

3.3. Виділення пам'яті для кожного лівого листка дерева, визначення значення лівого листка;

3.4. Виділення пам'яті для кожної нової вершини, занесення результату виконання операцій до пам'яті;

3.5. Переадресування покажчиків на праву та ліву вершини дерева.

4. Вивід дерева результатів:

4.1. Вивід кореня дерева;

4.2. Циклічний вивід проміжних вершин від кореня до термінальних вершин.

5. Кінець.

Приклад: Вираз 5+12*4. Дерево + . Кількість рівнів визначається при /\ вводі виразу. На екран виводиться

5 * відображення дерева.

/\

12 4

uses crt;

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

tree=record

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

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

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

end;

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

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

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

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

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

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

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

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

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

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

procedure form_ar;

begin

repeat

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

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

begin

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

операцiя}

begin

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

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

end

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

begin

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

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

занесення до масиву чисел}

end;

end; {end for}

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

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

end;

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

procedure enter_tree;

begin

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

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

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

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

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;

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

procedure solution;

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

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

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

порожнi}

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

begin

case mc[i] of {вибiр та виконання операцiй вiдповiдно до

вузлових вершин}

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

елементiв,}

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

одного рiвня}

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

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

end;

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

дерева}

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

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

k^.right:=nil;

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

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

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

операцiй}

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

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

end;

end;

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

procedure print_tree;

begin

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

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

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

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

begin

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

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

вершини}

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

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

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

поточної вершини}

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

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

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

end;

gotoxy(1,23);

end;

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

begin clrscr;

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

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

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

writeln('enter syntax tree, press n to finish:');

form_ar; {формування масивiв вузлових та термiнальних

вершин дерева}

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

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

вузлах дерева}

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

readln;

end.