Алгоритмы обхода бинарных деревьев

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

Полный обход дерева дает линейную расстановку узлов, что облегчает выполнение многих алгоритмов. Существует три принципа упорядочения, которые естественно вытекают из структуры дерева. Как и саму древовидную структуру, их удобно выразить с помощью рекурсии. Им соответсвуют три левосторонних алгоритма обхода.

Нисходящий (прямой) обход выполняется по формуле “корень-левый-правый” (К-Л-П).

обработать корневой узел;

обойти левое поддерево в нисходящем порядке;

обойти правое поддерево в нисходящем порядке.

Трасса нисходящего обхода дерева рис. 68: A B C D E F.

Восходящий (концевой) обход выполняется по формуле “ левый-правый-корень” (Л-П-К).

обойти левое поддерево в восходящем порядке;

обойти правое поддерево в восходящем порядке;

обработать корневой узел.

Трасса восходящего обхода дерева рис. 68 C D B F E A.

Смешанный (обратный) обход выполняется по формуле “ левый—корень-правый” (Л-К-П).

обойти левое поддерево в смешанном порядке;

обработать корневой узел;

обойти правое поддерево в смешанном порядке.

Трасса смешанного обхода дерева рис. 68: С B D A E F.

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

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

Procedure KLP(root: PTree);	{ root – указатель на корень дерева }
begin
if root <> nil then begin	{ дерево не пусто? }
writeln(root^.info);	{ распечатать информ. поле корневого узла }
KLP(root^.left);	{ обойти левое поддерево в нисходящем порядке }
(* 1 *) KLP(root^.right)	{ обойти правое поддерево в нисходящем порядке }
(* 2 *) end;
(* 3 *) end;

Таблица 4. Трасса состояний стека при работе процедуры нисходящего обхода бинарного дерева

Номер входа в процедуру	Номер уровня рекур- сии	Значение фактичес-кого параметра	Стек	Выход-ная трасса	Выход из уровня
Исходное состояние	Конечное состояние
		^A	(-,-)	(^A, *1*)	A
		^B	(^A, *1*)	(^B, *1*) (^A, *1*)	B
		^C	(^B, *1*) (^A, *1*)	(^C, *1*) (^B, *1*) (^A, *1*)	C
		NIL	(^C, *1*) (^B, *1*) (^A, *1*)	(NIL,*1*) (^C, *1*) (^B, *1*) (^A,*1*)
	NIL	(NIL,*1*) (^C, *1*) (^B, *1*) (^A,*1*)	(^C, *1*) (^B, *1*) (^A, *1*)		(*3*)
	^C	(^C, *1*) (^B, *1*) (^A, *1*)	(^C, *2*) (^B, *1*) (^A, *1*)
		NIL	(^C, *2*) (^B, *1*) (^A, *1*)	(NIL,*2*) (^C, *2*) (^B, *1*) (^A, *1*)
	NIL	(NIL,*2*) (^C, *2*) (^B, *1*) (^A, *1*)	(^C, *2*) (^B, *1*) (^A, *1*)		(*3*)
	^C	(^C, *2*) (^B, *1*) (^A,*1*)	(^B, *1*) (^A, *1*)		(*3*)
	^B	(^B, *1*) (^A,*1*)	(^B, *2*) (^A, *1*)
		^D	(^B,*2*) (^A,*1*)	(^D, *1*) (^B, *2*) (^A, *1*)	D
		NIL	(^D, *1*) (^B, *2*) (^A, *1*)	(NIL,*1*) (^D, *1*) (^B, *2*) (^A, *1*)
	NIL	(NIL,*1*) (^D, *1*) (^B, *2*) (^A, *1*)	(^D, *1*) (^B, *2*) (^A, *1*)		(*3*)
	^D	(^D, *1*) (^B, *2*) (^A, *1*)	(^D, *2*) (^B, *2*) (^A, *1*)
		NIL	(^D, *2*) (^B, *2*) (^A, *1*)	(NIL,*2*) (^D, *2*) (^B, *2*) (^A, *1*)
	NIL	(NIL,*2*) (^D, *2*) (^B, *2*) (^A, *1*)	(^D, *2*) (^B, *2*) (^A, *1*)		(*3*)
	^D	(^D, *2*) (^B, *2*) (^A, *1*)	(^B, *2*) (^A, *1*)		(*3*)
	^B	(^B, *2*) (^A, *1*)	(^A, *1*)		(*3*)
	^A	(^A, *1*)	(^A, *2*)
		^E	(^A, *2*)	(^E, *1*) (^A, *2*)	E
		NIL	(^E, *1*) (^A, *2*)	(NIL,*1*) (^E, *1*) (^A, *2*)
	NIL	(NIL,*1*) (^E, *1*) (^A, *2*)	(^E, *1*) (^A, *2*)		(*3*)
	^E	(^E, *1*) (^A, *2*)	(^E, *2*) (^A, *2*)
Номер входа в процедуру	Номер уровня рекур- сии	Значение фактичес-кого параметра	Исходное состояние стека	Конечное состояние стека	Выход-ная трасса	Выход из уровня
		^F	(^E, *2*) (^A, *2*)	(^F, *1*) (^E, *2*) (^A, *2*)	F
		NIL	(^F, *1*) (^E, *2*) (^A, *2*)	(NIL, *1*) (^F, *1*) (^E, *2*) (^A, *2*)
	NIL	(NIL, *1*) (^F, *1*) (^E, *2*) (^A, *2*)	(^F, *1*) (^E, *2*) (^A, *2*)		(*3*)
	^F	(^E, *2*) (^A, *2*)	(^F, *2*) (^E, *2*) (^A, *1*)
		NIL	(^F, *2*) (^E, *2*) (^A, *2*)	(NIL, *2*) (^F, *2*) (^E, *2*) (^A, *2*)
	NIL	(NIL, *2*) (^F, *2*) (^E, *2*) (^A, *2*)	(^F, *2*) (^E, *2*) (^A, *2*)		(*3*)
	^F	(^F, *2*) (^E, *2*) (^A, *2*)	(^E, *2*) (^A, *2*)		(*3*)
	^E	(^E, *2*) (^A, *2*)	(^A, *2*)		(*3*)
	^A	(^A, *2*)	(-, -)		(*3*)

Для иллюстрации работы этой процедуры и построения трассы состояний стека будем использовать следующие обозначения:

^A – адрес узла дерева, в информационном поле которого хранится символ “A”;

(* 1 *) и (* 2 *) – адреса возврата из уровня рекурсивной процедуры, номер которой на 1 больше текущего;

(* 3 *) – адрес возврата из рекурсивной процедуры текущего уровня.

Трасса нисходящего обхода дерева, приведенного на рис. 68, содержится в таблице 4.