1. Формирование бинарного дерева

Листинг 1.

ТУРЕ { ОПИСАНИЕ ДЕРЕВА }

NODE = ^TREE; { ТИП УКАЗАТЕЛЯ УЗЛА ДЕРЕВА }

TREE = RECORD { СТРУКТУРА УЗЛА БИНАРНОГО ДЕРЕВА }

LEFT :^TREE; { УКАЗАТЕЛЬ ЛЕВОГО ПОДДЕРЕВА }

RIGHT :^TREE; { УКАЗАТЕЛЬ ПРАВОГО ПОДДЕРЕВА }

IDENT : CHAR; { ИДЕНТИФИКАТОР УЗЛА ПЕРЕВА }

END; PROCEDURE CREATE(VAR A:NODE);

{ РЕКУРСИВНАЯ ПРОЦЕДУРА СОЗДАНИЯ В ОПЕРАТИВНОЙ ПАМЯТИ

СТРУКТУРЫ БИНАРНОГО ДЕРЕВА В ПЕРЕМЕННОЙ "А" ФОРМИРУЕТСЯ АДРЕС КОРНЯ ПОЛУЧЕННОГО ДЕРЕВА ИЛИ ПОДДЕРЕВА }

VAR

В : NODE; { АДРЕС ПОДДЕРЕВА ДАННОГО УЗЛА }

R : CHAR; { РАБОЧАЯ ПЕРЕМЕННАЯ }

BEGIN

NEW(A); { РЕЗЕРВИРОВАНИЕ ПАМЯТИ ДЛЯ НОВОГО УЗЛА ДЕРЕВА } WRITE(‘ ВВЕДИТЕ ИМЯ УЗЛА> ’);

READLN(A^.IDENT);

WRITE(‘ ЕСТЬ ЛЕВОЕ ПОДДЕРЕВО У УЗЛА ‘,А^.IDENT,’ ? (Y/N) ‘);

READLN(R); IF (R='Y') THEN

BEGIN

CREATE(B); { ФОРМИРОВАНИЕ ЛЕВОГО ПОДДЕРЕВА УЗЛА }

A^.LEFT:=B;

END ELSE

A^.LEFT:=NIL; { У ДАННОГО УЗЛА НЕТ ЛЕВОГО ПОДДЕРЕВА }

WRITE(‘ ЕСТЬ ПРАВОЕ ПОДДЕРЕВО У УЗЛА ’,A^.IDENT,’ ? (Y/N) ‘);

READLN(R);

IF (R='Y') THEN BEGIN

CREATE(В); { ФОРМИРОВАНИЕ ПРАВОГО ПОДДЕРЕВА УЗЛА }

A^.RIGHT:=B; END ELSE

A^.RIGHT:=NIL; { У ДАННОГО УЗЛА НЕТ ПРАВОГО ПОДДЕРЕВА } END;

2. Рекурсивная процедура обхода узлов дерева сверху-вниз

Листинг 2.

PROCEDURE PREORDER(A:NODE);

BEGIN

IF A<>NIL THEN BEGIN

WRITE(A^.IDENT:2); { ПЕЧАТЬ ИДЕНТИФИКАТОРА УЗЛА } PREORDER(A^.LEFT); { ОБХОД ЛЕВОГО ПОДДЕРЕВА }

PREOROER(A^.RIGHT); { ОБХОД ПРАВОГО ПОДДЕРЕВА }

END; END;

В процедуре CREATE функция NEW(A) резервирует в памяти ПЭВМ область для размещения записи типа TREE. В операторе вводится идентификатор текущего узла дерева (один символ) и заносится в поле IDENT записи, адрес которой в данный момент хранятся в переменной A. Далее на экран выдается запрос, есть ли левое поддерево у данного узла. Если в ответ введён символ Y (да), то рекурсивно вызывается процедура CREATE для формирования левого поддерева. После ее завершения в переменной B возвращается адрес узла – корня левого поддерева и он запоминается в поле LEFT текущей записи.

Аналогично формируется правое поддерево. Выход из рекурсии происходит при обработке концевых вершин дерева. В записи, представляющей эти узлы, в поля LEFT и RIGHT заносится константа NIL - неопределенный адрес.

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

составляющие его правое поддерево. Тогда алгоритм обхода бинарного дерева в порядке сверху вниз имеет следующий вид.

Шаг I. Посетить корень дерева (напечатать его идентификатор),

Шаг 2. Пройти сверху вниз левое поддерево корневого узла.

Шаг 3. Пройти сверху вниз правое поддерево.

Описанный алгоритм реализуется в приведенном примере рекурсивной процедурой. Условие A ≠ NIL позволяет обнаружить концевые вершены дерева и обеспечивает выход из рекурсии.

В основной программе выполняется последовательное обращение к описанным выше подпрограммам создания и обхода бинарного дерева. Заметим, что начальное значение переменной указателя ROOT определяется в процедуре CREATE. Это значение используется для указания адреса корневого узла сформированного бинарного дерева при обращении к процедуре обхода его узлов в порядке сверху вниз.