Восходящий обход ( Postorder, r_postorder )

Трудность заключается в том, что в отличие от Preorder в этом алгоритме каждая вершина запоминается в стеке дважды: первый раз - когда обходится левое поддерево, и второй раз - когда обходится правое поддерево. Таким образом, в алгоритме необходимо различать два вида стековых записей: 1-й означает, что в данный момент обходится левое поддерево; 2-й - что обходится правое, поэтому в стеке запоминается указатель на узел и признак (код-1 и код-2 соответственно).

Алгоритм восходящего обхода можно представить следующим образом:

· 1) Спуститься по левой ветви с запоминанием вершины в сте ке как 1-й вид стековых записей;

· 2) Если стек пуст, то перейти к п.5;

· 3) Выбрать вершину из стека, если это первый вид стековых записей, то возвратить его в стек как 2-й вид стековых запи сей; перейти к правому сыну; перейти к п.1, иначе перейти к п.4;

· 4) Обработать данные вершины и перейти к п.2;

· 5) Конец алгоритма.

Текст программы процедуры восходящего обхода (Postorder) представлен в программном примере 6.8.

{=== Программный пример 6.8. Восходящий обход ====}

Procedure Postorder (t: TreePtr);

label 2;

Var

p: TreePtr;

top: point; { стековый тип }

Sign: byte; { sign=1 - первый вид стековых записей}

{ sign=2 - второй вид стековых записей}

Begin (*------------- Инициализация ------------------*)

if t = nil then

begin writeln('Дерево пусто'); exit; end

else begin p:=t; top:=nil; end; {инициализация стека}

(*------- Запоминание адресов вдоль левой ветви -------*)

2: while p <> nil do

begin s_Push(top,1,p); { заносится указатель 1-го вида}

p:=p^.left; end;

(*-- Подъем вверх по дереву с обработкой правых ветвей ----*)

while top <> nil do

begin p:=s_Pop(top,sign); if sign = 1 then

begin s_Push(top,0,p); { заносится указатель 2-го вида }

p:=p^.right; goto 2; end

else (*---- Обработка данных звена ---------*)

................................

end; End; { Postorder }