Обход деревьев с помощью стека

В языках без рекурсии для обхода деревьев используется стек. Фактически, и рекурсия реализуется на основе стека, но программист не принимает в этом непосредственного участия. Явное применение стека иногда целесообразно и в качестве альтернативного к рекурсии варианта, поскольку дает больший контроль в распределении памяти и не создает трудностей при отладке. Приведем процедуру выдачи на экран номеров вершин дерева в порядке обхода сверху вниз с явным использованием стека. Применяемые переменные были описаны в предыдущей программе.

Procedure PechPrSt(T: ukaz);

Type

point=^stek;

stek=record

Ver: ukaz;

Next: point;

Ns: integer { номер сына, по которому пошли вниз }

end;

Var

Top, Kon: point;

K: ukaz;

Procedure Dob(P: ukaz);

Begin

New(kon);

Kon^.Ver:=P;

Kon^.Next:=Top;

Kon^.Ns:=0;

Top:=Kon;

End;

Procedure Udal;

Begin

Kon:=Top;

Top:=Top^.Next;

Dispose(Kon);

End;

Begin { начало процедуры PechPrSt }

Top:=Nil;

K:=T;

Dob(K); { занесение в стек корня }

WriteLn('Вершина ', Top^.Ver^.Key);

While Top<>Nil do

begin

Top^.Ns:=Top^.Ns+1;

case Top^.Ns of

1: if Top^.Ver^.Left<>Nil then

begin

Dob(Top^.Ver^.Left);

WriteLn('Вершина ', Top^.Ver^.Key);

end;

2: if Top^.Ver^.Right<>Nil then

begin

Dob(Top^.Ver^.Right);

WriteLn('Вершина ', Top^.Ver^.Key);

end;

3: Udal

end

end

End;

Последовательность прохода по сыновьям обеспечивается счетчиком Ns. Номер вершины выдается на экран при первом посещении этой вершины, то есть при добавлении вершины в стек.

Для реализации обхода снизу вверх требуются незначительные изменения. Сейчас номер вершины нужно выдавать при последнем ее посещении, то есть перед удалением из стека. Аналогично, при обходе слева направо выдача должна быть после посещения первого (левого) сына.