Cмешанный обход (inorder, r_inorder).



CМЕШАННЫЙ ОБХОД (Inorder, r_Inorder).

Смешанный обход можно описать следующим образом:

  • 1) Спуститься по левой ветви с запоминанием вершин в стеке;
  • 2) Если стек пуст то перейти к п.5;
  • 3) Выбрать вершину из стека и обработать данные вершины;
  • 4) Если вершина имеет правого сына, то перейти к нему; перейти к п.1.
  • 5) Конец алгоритма.

В программном примере 6.6. реализован алгоритм смешанного обхода дерева.

{=== Программный пример 6.6. Процедура смешанного обхода ===} Procedure Inorder (t: TreePtr); label 1; 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 p:=t; st:=nil; end; 1: while p^.left <> nil do begin (* Спуск по левой ветви и заполнение очереди *) Push_st(st,p); p:=p^.left; end; if st = NIL { контроль заполнения стека } then exit; p:=Pop_st(st);{выборка очередного элемента на обработку} (*--------------- Обработка данных звена --------------*) ................................ if p^.right <> nil then begin p:=p^.right; { переход к правой ветви } goto 1; end; End; { Inorder }

Трассировка смешанного обхода приведена в табл. 6.2:



Содержание раздела