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

   В случае ЛКП-обхода также возможно некоторое упрощение − в стеке со-
храняются указания лишь на операции 1 или 2:
procedure обход_ЛКП ( b: BTree ); {обратный}
  var S: Stack of ( BTree , operation );
        p: BTree; op: operation { =1..2};
begin S:= Create; S ← ( b , 1);
  while not Null ( S ) do
  begin ( p , op ) ← S;
     if op = 1 then
     begin
         S ← ( p , 2) ; if not Null ( Left ( p ) ) then S ← ( Left ( p ) , 1 )
     end
     else {op=2}
     begin
         посетить ( p ); if not Null ( Right ( p ) ) then S ← ( Right ( p ) , 1 )
     end
end{while}
end{обход_ЛКП}
   Конкретизация общего алгоритма для ЛПК-обхода (здесь нет упрощений)
имеет вид:
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) ; if not Null ( Left ( p ) ) then S ← ( Left ( p) , 1 )
     end
     else if op = 2 then
     begin
         S ← ( p, 3); if not Null (Right ( p ) ) then S ← ( Right ( p ) , 1 )
     end else { op=3 } посетить ( p )
  end{while}
end{обход_ЛПК}

   Еще один полезный способ обхода бинарного дерева − обход в горизон-
тальном порядке (в ширину). При таком способе узлы бинарного дерева про-
ходятся слева направо, уровень за уровнем от корня вниз (поколение за поко-
лением от старших к младшим). Легко указать нерекурсивную процедуру
горизонтального обхода, аналогичную процедуре КЛП-обхода (в глубину), но
использующую очередь вместо стека:
                                       53