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:

Таблица 6.2

Рекурсивный смешанный обход описывается следующим образом:

· 1) Смешанный обход левого поддерева;

· 2) Обработка корневой вершины;

· 3) Смешанный обход правого поддерева.

Текст программы рекурсивной процедуры (r_Inorder) демонстрируется в программном примере 6.7.

{=== Программный пример 6.7. Рекурсивное выполнение смешанного обхода ===}

Procedure r_Inorder(t: TreePtr);

begin

if t = nil then

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

if t^.left <> nil then R_inorder (t^.left);

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

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

if t^.right <> nil then R_inorder(t^.right);

End;