program lab7_2;
uses crt, graph; { пiдключення модулiв }
type TED = integer; { тип елементу }
tree =^ top; { дерево }
top = record { вершина }
e: TED; { елемент }
l, r: tree; { лiва та права гiлки }
end;
var grdriver, grmode, errcode: integer; { для графiки }
r: TED; { елемент для пошуку }
t: tree; { дерево }
procedure insert(var t: tree); { додавання елемента в дерево }
var ch: char; { код клавiшi }
e: TED; { елемент }
begin
write('Введiть значення: ');
readln(e); { отримуємо значення елемента }
if t = nil then begin
new(t); { видiляємо пам'ять }
t^.e := e; { заносимо елемент }
t^.l := nil;
t^.r := nil
end;
write('Є лiва гiлка? ');
ch := readkey; { отримуємо код клавiшi }
if ch = #13 then insert(t^.l) { якщо Enter - викликаємо саму себе для створення лiвої гiлки }
else writeln('Нема.');
write('Є права гiлка? ');
ch := readkey; { отримуємо код клавiшi }
if ch = #13 then insert(t^.r) { якщо Enter - викликаємо саму себе для створення правої гiлки }
else writeln('Нема.');
end;
procedure draw(t: tree); { малювання дерево }
var start_x, start_y: integer; { початковi координати }
e: string; { елемент для виведення }
const delx = 30; { вiдстань мiж елементами по x }
dely = 30; { вiдстань мiж елементами по y }
circle_r = 10; { радiус кола }
btw = circle_r div 2; { половина радiуса }
procedure print_node(t: tree; level: integer; l, c, r: integer); { вивелення вузла }
function min(a, b: integer): integer; { мiнiмальне значення мiж двома числами }
begin
min := a;
if b < a then min := b
end;
function center(a, b: integer): integer; { центр }
begin
center := min(a,b) + abs(a-b) div 2
end;
var pos_y: integer; { позицiя по осi y }
begin
pos_y := start_y + pred(level) * dely; { знаходимо позицiю по осi y поточного вузла }
if t^.r <> nil then begin { якщо є права гiлка - малюємо її i все пiддерево }
line(c,pos_y,center(c,r),pos_y+dely); { малюємо лiнiю, що сполучає поточний вузол з правим пiддеревом }
print_node(t^.r,level+1,c+btw,center(c+btw,r-btw),r-btw); { викликаємо саму себе для малювання правого пiддерева }
end;
if t^.l <> nil then begin { якщо є лiва гiлка - малюємо її i все пiддерево }
line(c,pos_y,center(l,c),pos_y+dely); { малюємо лiнiю, що сполучає поточний вузол з лiвим пiддеревом }
print_node(t^.l,level+1,l+btw,center(l+btw,c-btw),c-btw); { викликаємо саму себе для малювання лiвого пiддерева }
end;
{ малюємо вузол }
setcolor(black); { встановлюємо колiр }
setfillstyle(solidfill,black); { шаблон заповнення i колiр }
pieslice(c,pos_y,0,359,circle_r); { малюємо сектор кола }
setcolor(white); { встановлюємо колiр }
circle(c,pos_y,circle_r); { малюємо коло }
settextjustify(centertext,centertext); { вирiвнюємо по центру }
str(t^.e:1,e); { перетворення числа в рядок }
outtextxy(c,pos_y,e); { виведення елемента }
end;
begin
start_x := getmaxx div 2; { координата по x - центр }
start_y := 10; { координата по y }
print_node(t,1,100,getmaxx div 2,getmaxx-100); { вивелення головного вузла }
end;
procedure print(t: tree; x, y: integer); { друк дерева }
begin
if t <> nil then begin { якщо не кiнець дерева }
print(t^.r,x+((80 div succ(y)) div 2), succ(y)); { викликаємо саму себе для друку правої гiлки }
gotoxy(x,2*y); { змiнюємо позицiю курсору }
write(t^.e); { виводимо значення елемента }
print(t^.l,x-((80 div succ(y)) div 2), succ(y)); { викликаємо саму себе для друку лiвої гiлки }
end;
end;
function count(t: tree; r: TED): integer; { пiдрахування кiлькостi входжень елемента }
var n: integer; { лiчильник входжень }
begin
n := 0; { обнуляємо лiчильник }
if t <> nil then begin { якщо не кiнець дерева }
if t^.e = r then inc(n); { якщо поточний елемент дорiвнює шуканому, збiльшуємо лiчильник }
n := n + count(t^.l,r); { викликаємо саму себе для пошуку у лiвiй гiлцi }
n := n + count(t^.r,r) { у правiй }
end;
count := n { повертаємо значення лiчильника }
end;
procedure remove(var t: tree); { звiльнення пам'ятi }
begin
if t <> nil then begin { якщо не кiнець дерева }
if t^.r <> nil then remove(t^.l); { викликаємо саму себе для лiвої гiлки }
if t^.l <> nil then remove(t^.r); { для правої }
dispose(t) { звiльняємо пам'ять }
end
end;
begin
clrscr; { очищаємо екран }
insert(t); { заповнюємо дерево }
clrscr; { очищаємо екран }
grdriver := detect; { встановлюємо графiчний драйвер }
initgraph(grdriver,grmode,''); { iнiцiалiзуємо графiку }
errcode := graphresult; { отримуємо код завершення процедури }
if errcode <> grok then begin { якщо виникла помилка iнiцiалiзацii }
writeln('Дерево:');
print(t,40,2); { друкуємо дерево }
gotoxy(1,23); { змiнюємо позицiю курсору }
end
else begin { якщо графiка iнiцiалiзувалася }
draw(t); { малюємо дерево }
readkey; { чекаємо поки користувач натисне клавiшу }
closegraph; { вимикаємо графiчний режим }
end;
write('Введiть шуканий елемент: ');
readln(r); { отримуємо елемент для пошуку }
writeln('Кiлькiсть входжень елемента: ',count(t,r)); { виводимо результат }
remove(t); { звiльняємо пам'ять вiд дерева }
readkey { чекаємо поки користувач натисне клавiшу }
end. |
