Нисходящий обход (preorder, r_preorder)

В соответствии с алгоритмом, приведенным выше, текст процедуры имеет вид:

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

Procedure Preorder (t: TreePtr);

Type

Stack=^Zveno;

Zveno = record

next: Stack;

el: pointer;

end;

Var

st: stack;

p: TreePtr;

(*------------ Процедура занесения в стек указателя ------*)

Procedure Push_st (var st:stack; p:pointer);

Var

q: stack;

begin new(q); q^.el:=p; q^.next:=st; st:=g; end;

(*----------- Функция извлечения из стека указателя ------*)

Function Pop_st (var st: stack):pointer;

Var

e,p: stack;

begin Pop_st:=st^.el; e:=st; st:=st^.next; dispose(e); end;

Begin

if t = NIL then

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

else begin st:=nil; Push_st(St,t); end;

while st <> nil do { контроль заполнения стека }

begin p:=Pop_st(st);

while p <> nil do

begin { Обработка данных звена }

if p^.right <> nil

then Push_st(st,p^.right);

p:=p^.left;

end; end;

End; { Preorder }

Трассировка нисходящего обхода приведена в табл.6.1:

Таблица 6.1