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 ('найден дубль

включаемого элемента');

readln;

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 { огранчитель рекурсии }