Виды бинарных деревьев

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

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

Рис. 68. Связанное представление бинарного дерева

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Трасса смешанного обхода дерева рис. 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;

Номер входа в процедуру	Номер уровня рекур- сии	Значение фактичес-кого параметра	Стек	Выход-ная трасса	Выход из уровня
Исходное состояние	Конечное состояние
		^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.