9.3.4. Алгоритм симметричного обхода бинарного дерева

Реализация обходов бинарного дерева с помощью рекурсивной процедуры не вы­зывает затруднений. В некоторых случаях из соображений эффективности при­менение явной рекурсии оказывается нежелательным. Следующий очевидный алгоритм реализует наиболее популярный симметричный обход без рекурсии, но с использованием стека.

Алгоритм 9.1. Алгоритм симметричного обхода бинарного дерева

Вход: бинарное дерево, представленное списочной структурой, r — указатель на корень. Выход: последовательность узлов бинарного дерева в порядке симметричного обхода.

Т: = ; р: = r { вначале стек пуст и р указывает на корень дерева }

М : { анализирует узел, на который указывает р }

if р = nil then

if T = 0 then

stop { обход акончен }

end if

р  Т { левое поддерево обойдено }

yield р { очередной узел при симметричном обходе }

р:=р.r { начинаем обход правого поддерева

else

р  Т { запоминаем текущий узел ... }

р:=р.l { ... и начинаем обход левого поддерева }

end if

goto M