Пример 2. 5 writeln('4. Удаление элемента из дерева')

В качестве примера рассмотрим создание сбалансированного дерева и выполнение всех действий с элементами дерева: поиск заданного элемента в дереве, вставку любого нового элемента, удаление заданного элемента из дерева, вывод дерева в достаточно наглядной форме. Решение задачи состоит из двух файлов: основной программы и модуля, в котором описаны все названные действия над элементами дерева.

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);