New(q);

q^.inf1:=inf1;

q^.inf2:=inf2;

{значения полей передаются в качестве параметров}

q^.right:=nil;

q^.left:=nil;

End;

procedure Insert_el (p: nd; {адрес включаемого элемента}

var root: nd);

Var

q, t: nd;

Begin

if root = nil then

root:= p {элемент стал корнем}

Else

begin { поиск по дереву }

t:= root;

q:= root;

while (t < > nil) do

Begin

if p^.inf1 < t^.inf1 then

Begin

q:= t;{ запоминание текущего адреса}

t:= t^.left; {уход по левой ветви}

End

Else

if p^.inf1 > t^.inf1 then

Begin

q:= t;{ запоминание текущего адреса}

t:= t^.right; {уход по правой ветви}

End

Else

Begin

writeln ('найден дубль включаемого элемента');

exit; {завершение работы процедуры}

End

End;

{после выхода из цикла в q - адрес элемента, к которому

должен быть подключен новый элемент}

if p^.inf1 < q^.inf1 then

q^.left:= p {подключение слева }

Else

q^.right:= p; {подключение справа}

End;

ПРИМЕЧАНИЕ: элемент с дублирующим ключевым признаком в дерево не включается.

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

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

При посещении любого узла возможно однократное выполнение следующих трех действий:

1) обработать узел (конкретный набор действий при этом не важен). Обозначим это действие через О (обработка);

2) перейти по левой ссылке (обозначение - Л);

3) перейти по правой ссылке (обозначение - П).

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

На примере дерева на рис. 10 проиллюстрируем варианты обхода дерева.

1) Обход вида ОЛП. Такой обход называется «в прямом порядке», «в глубину». Он даст следующий порядок посещения узлов:

20, 10, 8, 15, 17, 35, 27, 24, 30

2) Обход вида ЛОП. Он называется «симметричным» и даст следующий порядок посещения узлов:

8, 10, 15, 17, 20, 24, 27, 30, 35

3) Обход вида ЛПО. Он называется «в обратном порядке» и даст следующий порядок посещения узлов:

8, 17, 15, 10, 24, 30, 27, 35, 20

Если рассматривать задачи, требующие сплошного обхода дерева, то для части из них порядок обхода, в целом, не важен, например, подсчет числа узлов дерева, числа листьев/не листьев, элементов, обладающих заданной информацией и т.д. Однако такая задача, как уничтожение бинарного дерева с освобождением памяти, требует использования только обхода «в обратном порядке».

Рассмотрим средства, с помощью которых можно обеспечить варианты обхода дерева.

При работе с бинарным деревом с точки зрения программирования оптимальным вариантом построения программы является использование рекурсии. Базисный вариант рекурсивной процедуры обхода бинарного дерева очень прост.

{ обход дерева по варианту ЛОП }

Procedure Recurs_Tree (q: nd);

Begin

If q <> nil Then

Begin

Recurs_Tree(q^.left);{уход по левой ветви-Л}

Work (q); { процедура обработки дерева-О}

Recurs_Tree(q^.right);{уход по правой ветви-П}

End;

End;

Рекурсия в этой программе действует точно так же, как и в рекурсивных процедурах работы со списками: создается цепочка процедур, каждая из которых рекурсивно обращается к себе и затем ожидает завершения вызванной процедуры. Потенциально бесконечный процесс рекурсивного вызова останавливается с помощью «ограничителя рекурсии», в данном случае им становится нарушение условия (q <> nil), когда при обходе обнаруживается «нулевая» ссылка вместо реального адреса. При этом начинается последовательное завершение вызванных процедур с возвратом управления в вызывающую. Способ обхода меняется с изменением порядка обращений к процедурам.

Для практической проработки действия механизма рекурсии при реализации вариантов обхода дерева можно воспользоваться уже построенным деревом с рис.10.

Пример использования рекурсивной процедуры при решении задачи подсчета листьев двоичного дерева.

Procedure Leafs_Count(q: nd; var k: integer);

Begin

If q <> nil Then

Begin

Leafs_Count(q^.left, k);

If (q^.left = nil) and (q^.right = nil) Then

K:= K +1;

Leafs_Count(q^.right, k);

End;

End;

{удаление дерева с освобождением памяти}

Procedure del_tree(q: nd);

Begin

if q<>nil then

Begin

del_tree (q^.left);

del_tree (q^.right);