Создание и редактирование бинарных деревьев
Begin
Begin
Begin
Begin
Begin
Begin
Begin
Begin
Var
Type
Implementation
Interface
Begin
Begin
Begin
Begin
Begin
Begin
Begin
Implementation
Interface
const stsize = 10; { предельный размер стека }
type data = ...; { элементы могут иметь любой тип }
procedure StackInit;
procedure StackClr;
function StackPush(a: data): Boolean;
function StackPop(var a: data): Boolean;
function StackSize: Integer;
var sta: array[1..stsize] of data; { данные стека }
{ Указатель на вершину стека,
работает на префиксное вычитание }
top: Integer;
{ инициализация - на начало }
procedure StackInit;
top:=stsize;
end;
{ очистка = инициализация }
procedure StackClr;
top:=stsize;
end;
{ занесение элемента в стек }
function StackPush(a: data): Boolean;
if top = 0 then
StackPush:=False else
{ занесение, затем - коррекция указателя }
sta[top]:=a;
top:=top-1;
StackPush:=True;
end;
end;
{ выборка элемента из стека }
function StackPop(var a: data): Boolean;
if top = stsizethen
StackPop:=False else
{ коррекция указатель, затем - выборка }
top:=top+1;
a:=sta[top];
StackPop:=True;
end;
end;
function StackSize: Integer; { определение размера }
StackSize:=stsize-top;
end;
end.
Модуль содержит вариант реализации стека на односвязном линейном списке.
unit stack;
type data = ...; { элементы могут иметь любой тип }
procedure StackInit;
procedure StackClr;
function StackPush(a: data): Boolean;
function StackPop(var a: data): Boolean;
function StackSize: Integer;
stptr = ^stit; { указатель на элемент списка }
stit = record{ элемент списка }
inf : data; { данные }
next: stptr; { указатель на следующий элемент }
end;
top: stptr; { указатель на вершину стека }
stsize: LongInt; { размер стека }
{ инициализация - список пустой }
procedure StackInit;
top:=nil;
stsize:=0;
end;
{ очистка - освобождение всей памяти }
procedure StackClr;
var x: stptr;
{ перебор элементов до конца списка и их уничтожение }
while top <> nil do
x:=top;
top:=top^.next;
Dispose(x);
end;
stsize:=0;
end;
function StackPush(a: data): Boolean; { занесение в стек }
var x: stptr;
{ если нет больше свободной памяти –
отказ; использовать только для BP 7.0 }
if MaxAvail < SizeOf(stit) then
StackPush:=False else
{ выделение памяти для элемента и заполнение информационной части }
New(x);
x^.inf:=a;
{ новый элемент помещается в голову списка }
x^.next:=top;
top:=x;
stsize:=stsize+1; { коррекция размера }
StackPush:=True;
end;
end;
function StackPop(var a: data): Boolean; { выборка элемента из стека }
var x: stptr;
{ список пуст - стек пуст }
if top = nil then
StackPop:=False else
{ выборка информации из первого элемента списка }
a:=top^.inf;
{ первый элемент исключается из списка, освобождается память }
x:=top;
top:=top^.next;
Dispose(x);
stsize:=stsize-1; { коррекция размера }
StackPop:=True;
end;
end;
function StackSize: Integer; { определение размера стека }
StackSize:=stsize;
end;
end.
Пример демонстрирует способ создания и элементарные операции по изменению и просмотру структуры бинарного дерева.
program BinTree;
{$APPTYPE CONSOLE}