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

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