В качестве примера рассмотрим создание сбалансированного дерева и выполнение всех действий с элементами дерева: поиск заданного элемента в дереве, вставку любого нового элемента, удаление заданного элемента из дерева, вывод дерева в достаточно наглядной форме. Решение задачи состоит из двух файлов: основной программы и модуля, в котором описаны все названные действия над элементами дерева.
Program Number_2_5;
uses crt,prg11;
Var
tree:ttree;
c:integer;
procedure pause;
Begin
write('Нажмите любую клавишу для продолжения');
readkey;
while keypressed do readkey;
end;
procedure menu;
Begin
clrscr;
writeln(' Выберите действие');
writeln('1. Создание дерева');
writeln('2. Вывод дерева на экран');
writeln('3. Нахождение требуемого элемента');
writeln('4. Удаление элемента из дерева');
writeln('5. Добавление элемента в дерево');
writeln('6. Завершение работы');
writeln;
Case readkey of
'1': begin
write ('Введите количество узлов дерева ');
readln(c);
tree.first:=tree.create(c);
clrscr;
gotoxy(30,10);
writeln('Дерево создано');
pause;
end;
'2': begin
tree.vivod(tree.first,0);
pause;
end;
'3': begin
write('Введите искомый элемент ');
|
|
readln(c);
tree.findel(tree.first,0,c);
tree.vivod(tree.first,0);
pause;
end;
'4': begin
write('Введите удаляемый элемент ');
readln(c);
tree.delel(tree.first,c);
pause;
end;
'5': begin
write('Введите новый элемент ');
readln(c);
tree.addel(c,tree.first);
tree.vivod(tree.first,0);
pause;
end;
'6': begin
write(' Завершение задачи ');
tree.done(tree.first);{Уничтожение дерева}
halt;
end;
end; end;
Begin
tree.init;
repeat menu until false;
End.
unit prg11;
Interface
Type
pnode=^node;
node= record
key:integer;
left,right:pnode;
end;{один элемент двоичного дерева}
ttree= object {объект, для работы со структурой
данных типа дерева}
n: integer;{число узлов в дереве}
f,first:pnode;
constructor init;
destructor done(var t:pnode);
function create(m:integer):pnode;
procedure vivod(var t:pnode;m:integer);
procedure findel(var t:pnode;m:integer;ikey:integer);
procedure delel(var t:pnode;ikey:integer);
procedure addel(ikey:integer;var t:pnode);
end;
Implementation
uses crt;
constructor ttree.init;
Begin
first:=nil;
n:=0;{создаем элемент пустого дерева}
end;
destructor ttree.done(var t:pnode);
Begin
if t<>nil then
Begin
with t^ do begin
done(left);
done(right);
end;
dispose(t);{Уничтожаем все дерево}
end;
end;
function ttree.create(m:integer):pnode;
var newnode:pnode;
x,nl,nr:integer;
Begin
n:=m;
if n=0 then
Begin
create:=nil;
exit;
end;
nl:=n div 2;
nr:=n-nl-1;
{Создаем сбалансированное дерево}
new(newnode);
with newnode^ do begin
write('Введите очередное число ');
readln(key);
left:=create(nl);
right:=create(nr);
end;
create:=newnode;
end;
procedure ttree.vivod(var t:pnode;m:integer);
var i: word;
Begin
if t<> nil then {процедура вывода дерева
также рекурсивна, как и функция для его создания}
with t^ do begin
vivod(left,m+1);
for i:=1 to m do write('***');
writeln(key);
vivod(right,m+1);