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

Описание программы

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

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

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;

• 3. Создание бинарного дерева:
  • — данные (целые числа) заносятся с клавиатуры;
  • — дубликаты не включаются (но выводятся на экран);
  • — признаком окончания ввода является ввод числа 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) известны, и алгоритм подставляет в это выражение значение, полученное на предыдущем шаге. Это происходит в процессе свертывания рекурсии.

Сформулируем два важных свойства рекурсивных алгоритмов:

1. Наличие тривиального случая.

Правильный рекурсивный алгоритм не должен создавать бесконечную последовательность вызовов самого себя. Для этого он обязательно должен содержать нерекурсивный выход: т. е. при некоторых входных данных вычисления в алгоритме должны производиться без вызовов его самого.

Для функции «факториал» тривиальный случай: «0≠1».

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;

Анализ приведенных алгоритмов показывает, что для получения ответа в них производится просмотр всех узлов дерева. Ниже будут приведены алгоритмы, в которых порядок обхода узлов дерева отличается. И в зависимости от порядка обхода узлов бинарного упорядоченного дерева, можно получить различные результаты, не меняя их размещения.

Просмотр используется не сам по себе, а для обработки элементов дерева, а просмотр сам по себе обеспечивает только некоторый порядок выбора элементов дерева для обработки. В приводимых ниже примерах обработка не определяется; показывается только место, в котором предлагается выполнить обработку текущего.

Алгоритмы просмотра дерева Самой интересной особенностью обработки бинарных деревьев является та, что при изменении порядка просмотра дерева, не изменяя его структуры, можно обеспечить разные последовательности содержащейся в нем информации. В принципе возможны всего четыре варианта просмотра: слева-направо, справа-налева, сверху-вниз и снизу-вверх.

Прежде чем увидеть, к каким результатам это может привести, приведем их.

Просмотр дерева слева — направо.

procedure ViewLR (Root:PNode); {LR -> Left — Right }.

begin.

if RootNil then.

begin.

ViewLR (Root^. left); {просмотр левого поддерева}.

{Операция обработки корневого элемента — вывод на печать, в файл и др.}.

ViewLR (Root^.right); { просмотр правого поддерева }.

end;

end;

Просмотр справа налево.

procedure ViewRL (Root:PNode); {LR -> Right — Left}.

begin.

if RootNil then.

begin.

ViewRL (Root^.right); { правого }ViewRL (Root^.left); { левого }.

end;

end;

Просмотр сверху — вниз.

procedure ViewTD (Root:PNode); {TD -> Top-Down}.

begin.

if RootNil then.

begin.

Операция обработки корневого элемента — вывод на печать, в файл и др.

ViewTD (Root^.left); {просмотр левого поддерева}.

ViewTD (Root^.right); { просмотр правого поддерева }.

end;

end;

Просмотр снизу-вверх.

procedure ViewDT (Root:PNode); {DT -> Down — Top}.

begin.

if RootNil then.

begin.

ViewDT (Root^.left); {просмотр левого поддерева}.

ViewDT (Root^.right); { просмотр правого поддерева }.

end;

end;

Поиск элемента в двоичном упорядоченном дереве.

function Search (SearchValue:integer;Root:PNode):PNode;

begin.

if (Root=Nil) or (Root^.Data=SearchValue) then.

Search := Root.

else if (Root^.Data > SearchValue) then.

Search := Search (SearchValue, Root^.left).

else.

Search := Search (SearchValue, Root^.right);

end;