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

Глава 2. Реализация операций по работе с бинарными деревьями

Деревья (как упорядоченные, так и нет) широко используются в программировании. По этой причине мы сосредоточимся в основном на рассмотрении процедур работы с ними.

2.1 Описание программы
Для описания узла бинарного дерева в программе введем тип, имеющий вид следующей записи:

type
PNode = ^TNode;

TNode = record
Info : string; {поле данных}
Left,Right : PNode; {указатели на левое и правое поддеревья}
end;
Процедура создания нового узла.
{ Создание нового узла со значением информационного поля X.
Возвращается указатель на новый узел}
function NewNode(X:string):PNode;
var
P : PNode;
begin
New(P);
P^.Info := X;
P^.Left := Nil;
P^.Roght := Nil;
NewNode := P;
end;

Процедура создания потомка (поддерева)

procedure SetLeft(P:PNode; X:string);
begin
P^.Left := NewNode(X);
end;
Создание бинарного дерева:
- данные (целые числа) заносятся с клавиатуры;
- дубликаты не включаются (но выводятся на экран);
- признаком окончания ввода является ввод числа 0;
- результат - бинарное упорядоченное дерево.
При обработке динамических структур типа «дерево» чаще всего используются рекурсивные алгоритмы.
Рекурсия предполагает определение некоторого понятия с использованием самого этого понятия. Никлаус Вирт приводит следующее утверждение о возможностях рекурсии:
При обработке динамических структур типа «дерево» чаще всего используются рекурсивные алгоритмы.
Рекурсия предполагает определение некоторого понятия с использованием самого этого понятия. Никлаус Вирт приводит следующее утверждение о возможностях рекурсии «… мощность рекурсии связана с тем, что она позволяет определить бесконечное множество объектов с помощью конечного высказывания».

Примером рекурсивного определения является факториал неотрицательного числа:

n! = 1 при n=0
n! = n*(n-1)! при n >0
В Турбо-Паскале рекурсия разрешена: подпрограмма может вызывать сама себя:
program FactDemo;
var
k : integer;
function Factor(n:integer):integer;
begin
if n=0 then
Factor : 1
else
Factor := n * Factor(n-1);
{end if}
end;
begin
write('Введите целое число ');
readln(k);
if k>=0 then
writeln('Факториал ',n:1,' = ', Factor(k));
{end if}
end.
Первое значение Factor вычисляется, когда n=0, оно подставляется в соответствующий экземпляр памяти. Теперь на каждом очередном шаге значения всех членов выражения n*Factor(n-1) известны, и алгоритм подставляет в это выражение значение, полученное на предыдущем шаге. Это происходит в процессе свертывания рекурсии.
Наличие тривиального случая. Правильный рекурсивный алгоритм не должен создавать бесконечную последовательность вызовов самого себя. Для этого он обязательно должен содержать нерекурсивный выход: т.е. при некоторых входных данных вычисления в алгоритме должны производиться без вызовов его самого.
Для функции «факториал» тривиальный случай: «0!=1».