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

ВОСХОДЯЩИЙ ОБХОД ( 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 }