Динамические структуры данных. Алексеев А.Ю - 52 стр.

ритм для всех трех порядков обхода использует стек S для хранения упорядо-
ченных пар ( p , n ), где p − узел бинарного дерева, а n - номер операции, кото-
рую надо применить к p, когда пара ( p , n ) будет выбрана из стека. Операции
“посетить корень”, “пройти левое поддерево”, “пройти правое поддерево” ну-
меруются числами 1,2,3 в зависимости от порядка их выполнения в данном
варианте обхода. В алгоритме эти операции будут реализованы следующим
образом:
 посетить корень – посетить ( p );
 пройти левое поддерево -
             if not Null ( Left ( p ) ) then S ← ( Left ( p ) , 1 );
 пройти правое поддерево -
             if not Null ( Right ( p ) ) then S ← ( Right ( p ) , 1 ).
Здесь и далее для краткости и наглядности использованы следующие обозна-
чения операций со стеком: S ← e вместо S := Push ( e , S ) и e ← S вместо Pop2
( e , S ).
     Тогда общий алгоритм имеет вид:
 procedure обход ( b: BTree );
    var S: Stack of ( BTree , operation ) ;
          p: BTree;      op: operation { =1..3};
 begin
    S:= Create; S ← ( b , 1);
    while not Null ( S ) do
    begin ( p , op ) ← S;
       if op = 1 then begin S ← ( p , 2); операция 1 end
       else if op = 2 then begin S ← ( p , 3); операция 2 end
       else { op = 3 }                          операция 3
    end{while}
 end{обход}
     В случае КЛП-обхода можно существенно упростить алгоритм, исключая
лишние для этого варианта манипуляции со стеком. Здесь нет необходимости
хранить в стеке номер операции. Итак, конкретизация (с упрощением) общего
алгоритма для КЛП-обхода имеет вид:
 procedure обход_КЛП ( b: BTree ); {прямой}
    var S: Stack of BTree; p: BTree;
 begin
      S:= Create; S ← b;
      while not Null ( S ) do
      begin
         p ← S;
         посетить ( p );
         if not Null ( Right ( p ) ) then S ← Right ( p );
         if not Null ( Left ( p ) ) then S ← Left ( p )
      end{while}
 end{обход_КЛП}
                                      52