Создание и редактирование бинарных деревьев
Пример демонстрирует способ создания и элементарные операции по изменению и просмотру структуры бинарного дерева.
program BinTree;
{$APPTYPE CONSOLE}
Type
PNode = ^TNode;
TNode = record
Name: string;
Left, Right: Pointer;
end;
Var
n: Integer;
s: string;
pnt, Current: PNode;
pnt_s, Current_s, Root: Pointer;
{ Сменить текущий узел }
procedure NodeSearch(pnt_s: Pointer; var Current_s: Pointer);
var pnt_n: PNode;
Begin
pnt_n:=pnt_s;
if pnt_n^.Name <> s then
Begin
if pnt_n^.Left <> nil then
NodeSearch(pnt_n^.Left,Current_s);
if pnt_n^.Right <> nil then
NodeSearch(pnt_n^.Right,Current_s);
End else
Current_s:=pnt_n;
end;
{ Вывод списка всех узлов дерева }
procedure NodeList(pnt_s: Pointer);
var pnt_n: PNode;
Begin
pnt_n:=pnt_s;
WriteLn(pnt_n^.Name);
if pnt_n^.Left <> nil then
NodeList (pnt_n^.Left);
if pnt_n^.Right <> nil then
NodeList(pnt_n^.Right);
end;
{ Удаление узла и всех его потомков в дереве }
procedure NodeDispose(pnt_s: Pointer);
var pnt_n: PNode;
Begin
if pnt_s <> nil then
Begin
pnt_n:=pnt_s;
WriteLn(pnt_n^.Name);
if pnt_n^.Left <> nil then
NodeDispose(pnt_n^.Left);
if pnt_n^.Right <> nil then
NodeDispose(pnt_n^.Right);
Dispose(pnt_n);
end;
end;
Begin
New(Current);
Root:=Current;
Current^.Name:='Root';
Current^.Left:=nil;
Current^.Right:=nil;
Repeat
WriteLn('Current node - ',Current^.Name);
WriteLn('1 - Set name for left descendant');
WriteLn('2 - Set name for right descendant');
WriteLn('3 - Change current node');
WriteLn('4 - Show node list');
WriteLn('5 - Delete descendantes of current node');
WriteLn('0 - Exit');
Read(n);
{ Создание левого потомка }
if n = 1 then
Begin
if Current^.Left = nil then
New(pnt) else
pnt:=Current^.Left;
WriteLn('Left name ?');
ReadLn;
Read(s);
pnt^.Name:=s;
pnt^.Left:=nil;
pnt^.Right:=nil;
Current^.Left:=pnt;
end;
{ Создание правого потомка }
if n = 2 then
Begin
if Current^.Right = nil then
New(pnt) else
pnt:=Current^.Right;
WriteLn('Right name ?');
ReadLn;
Read(s);
pnt^.Name:=s;
pnt^.Left:=nil;
pnt^.Right:=nil;
Current^.Right:=pnt;
end;
{ Сменить текущий узел }
if n = 3 then
Begin
WriteLn('New current node ?');
ReadLn;
Read(s);
Current_s:=nil;
NodeSearch(Root, Current_s);
if Current_s <> nil then
Current:=Current_s else
WriteLn('Node '''+s+''' not found');
end;
{ Вывод списка узлов }
if n = 4 then NodeList(Root);
{ Удаление поддерева }
if n = 5 then
Begin
WriteLn('l,r ?');
ReadLn;
Read(s);
if (s = 'l') then
{ Удаление левого поддерева }
Begin
pnt_s:=Current^.Left;
Current^.Left:=nil;
NodeDispose(pnt_s);
En d else
{ Удаление правого поддерева }
Begin
pnt_s:=Current^.Right;
Current^.Right:=nil;
NodeDispose(pnt_s);
end;
end;
until n = 0
end.
Дата добавления: 2021-12-14; просмотров: 293;