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

2.2 Определение сложного случая в терминах более простого.
При любых входных данных нерекурсивный выход должен достигаться за конечное число рекурсивных вызовов. Для этого каждый новый вызов рекурсивного алгоритма должен решать более простую задачу.
Иными словами рекурсивный алгоритм должен содержать определение некоторого сложного случая в терминах более простого случая.
Для функции «факториал» вместо вычисления n! заменяется умножением n*(n-1)!, и при этом с каждым вызовом значение n уменьшается, стремясь к нулю и достигая его за конечное число вызовов.
Из определения структуры типа «дерево» видно, что она рекурсивна по определению, а в силу этого рекурсивными являются и практически все алгоритмы работы с деревьями. Для этого достаточно посмотреть на приведенный выше пример создания бинарного упорядоченного дерева.
В процедуре Add имеется тривиальный случай (когда дерево пустое) и
рекурсивные вызовы: добавить в левое и правое поддеревья - Add (NewData,Root^.left) и Add(NewData,Root^.right).
Алгоритмы работы с деревьями
В приведенных ниже алгоритмах предполагается, что узел (элемент) дерева декларирован следующей записью:
Type
PNode = ^TNode;
TNode = record
Data : integer; {информационное поле}
left,right : PNode;
end;
Вычисление суммы значений информационных полей элементов. Алгоритм реализован в виде функции, возвращающей значение суммы информационных полей всех элементов. Тривиальным считается случай, когда очередной узел - пустой, и, следовательно, не имеет информационного поля.
function Sum(Root : PNode) : integer;
begin
if Root=Nil then {узел - пустой}
Sum := 0
else
Sum := Root^.Data + Sum(Root^.left)
+ Sum(Root^.right);
{end if}
end;
Для нетривиального случая результат вычисляется как значение информационного элемента в корне (Root^.Data) плюс суммы информационных полей левого и правого поддеревьев.
А выражение Sum(Root^.left)представляет собой рекурсивный вызов левого поддерева для данного корня Root.
А2. Подсчет количества узлов в бинарном дереве
function NumElem(Tree:PNode):integer;
begin
if Tree = Nil then
NumElem := 0
else
NumElem := NumElem(Tree^.left)+ NumElem(Tree^.right) + 1;
end;
Подсчет количества листьев бинарного дерева
function Number(Tree:PNode):integer;
begin
if Tree = Nil then
Number := 0 {дерево пустое - листов нет}
else if (Tree^.left=Nil) and (Tree^.right=Nil) then
Number := 1 {дерево состоит из одного узла - листа}
else
Number := Number(Tree^.left) + Number(Tree^.right);
{end if}
end;
Анализ приведенных алгоритмов показывает, что для получения ответа в них производится просмотр всех узлов дерева. Ниже будут приведены алгоритмы, в которых порядок обхода узлов дерева отличается. И в зависимости от порядка обхода узлов бинарного упорядоченного дерева, можно получить различные результаты, не меняя их размещения.
Просмотр используется не сам по себе, а для обработки элементов дерева, а просмотр сам по себе обеспечивает только некоторый порядок выбора элементов дерева для обработки. В приводимых ниже примерах обработка не определяется; показывается только место, в котором предлагается выполнить обработку текущего.
Алгоритмы просмотра дерева
Самой интересной особенностью обработки бинарных деревьев является та, что при изменении порядка просмотра дерева, не изменяя его структуры, можно обеспечить разные последовательности содержащейся в нем информации. В принципе возможны всего четыре варианта просмотра: слева-направо, справа-налева, сверху-вниз и снизу-вверх.
Прежде чем увидеть, к каким результатам это может привести, приведем
их.