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;
Дата добавления: 2015-09-11; просмотров: 21 | Поможем написать вашу работу | Нарушение авторских прав |