Материал: Мансуров. Основы программирования в среде Lazarus. 2010

Глава 4 Типовые алгоритмы обработки информации

____________________________________________________________________

p:= ptr_tree;

if not (p^.node = Elem) then begin

if p^.left <> nil then

search_node (Elem, p^.left, current_tree); if p^.right <> nil then

search_node (Elem, p^.right, current_tree);

end

else current_tree:= p;

end;

В процедуру передаются значение искомого узла Elem, само дерево

ptr_tree. Процедура возвращает ссылку на найденный узел current_tree.

Рекурсивная процедура удаления текущего поддерева:

procedure dispose_tree (ptr_tree: PTree); var

p: ^Tree; begin

if ptr_tree <> nil then begin

p:= ptr_tree;

if p^.left <> nil then begin

dispose_tree(p^.left); end;

if p^.right <> nil then begin

dispose_tree(p^.right);

381

4.3 Динамические структуры данных

____________________________________________________________________

end;

dispose(p);

end

end;

Рекурсивная процедура обхода двоичного дерева слева запишется на удив-

ление просто:

procedure obhod(p: PTree);

begin

if p<>nil then

begin

obhod(p^.left);

write(p^.node, ' ');

obhod(p^.right);

end;

end;

Реализуйте самостоятельно обход двоичного дерева слева по не рекурсив-

ному алгоритму 4.30!

Напишем программу ввода двоичного дерева с клавиатуры и его обхода слева:

program project1; {$mode objfpc}{$H+} uses

CRT, FileUtil; type

PTree= ^Tree; // Указатель на дерево

382

Глава 4 Типовые алгоритмы обработки информации

____________________________________________________________________

end; var

ptr_tree, current_tree, root: ^Tree; p, current: ^Tree;

s: string; choose: integer;

{Процедура поиска узла}

procedure search_node(Elem: string; ptr_tree:PTree;

var current_tree:PTree);

var

p: ^Tree; begin

p:= ptr_tree; writeln(p^.node);

if not (p^.node = Elem) then begin

if p^.left <> nil then

search_node (Elem, p^.left, current_tree); if p^.right <> nil then

search_node (Elem, p^.right, current_tree);

end

else current_tree:= p;

end;

{Процедура вывода дерева на экран}

383

4.3 Динамические структуры данных

____________________________________________________________________

procedure view_tree (ptr_tree: PTree); var

p: ^Tree; begin

p:= ptr_tree; writeln(p^.node);

if p^.left <> nil then view_tree(p^.left); if p^.right <> nil then view_tree(p^.right);

end;

{Процедура удаления текущего поддерева} procedure dispose_tree (ptr_tree:PTree); var

p: ^Tree; begin

if ptr_tree <> nil then begin

p:= ptr_tree; writeln(p^.node);

if p^.left <> nil then begin

dispose_tree(p^.left); end;

if p^.right <> nil then begin

dispose_tree(p^.right); end;

384

Глава 4 Типовые алгоритмы обработки информации

____________________________________________________________________

dispose(p); end

end;

procedure obhod(p: PTree); begin

if p <> nil then begin

obhod(p^.left); write(p^.node, ' '); obhod(p^.right);

end;

end; begin

writeln(UTF8ToConsole('введите номер или имя вершины'));

readln(s);

new(current);

root:= current;

current^.node:= s;

current^.left:= nil;

current^.right:= nil;

repeat

writeln;

writeln(UTF8ToConsole('Корень текущего подерева: '),

current^.node);

writeln(UTF8ToConsole('Выберите нужное действие:')); writeln(UTF8ToConsole('1-ввод левого поддерева')); writeln(UTF8ToConsole('2-ввод правого поддерева'));

writeln(UTF8ToConsole('3-сделать корень поддерева текущим'));

writeln(UTF8ToConsole('4-просмотреть дерево'));

385