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

определенный порядок перечисления узлов бинарного дерева. Выделяют не-
сколько стандартных вариантов обхода. Будем именовать их в зависимости от
того порядка, в котором при этом посещаются корень дерева и узлы левого и
правого поддеревьев. Например, при КЛП-обходе сначала посещается корень,
затем обходятся в КЛП-порядке последовательно левое и правое поддеревья.
Приведем рекурсивные процедуры КЛП-, ЛКП- и ЛПК-обходов, прямо соот-
ветствующие их рекурсивным определениям (операция обработки узла обо-
значена как “посетить(узел)”):

        procedure обходКЛП ( b: BTree ); {прямой}
        begin
          if not Null ( b )
          then begin
              посетить ( Root ( b ) );
              обходКЛП ( Left ( b ) );
              обходКЛП ( Right ( b ) );
          end
        end{обходКЛП};


 procedure обходЛКП ( b : BTree );        procedure обходЛПК ( b : BTree );
 {обратный}                                {концевой}
  begin                                   begin
    if not Null ( b ) then                  if not Null ( b ) then
    begin                                   begin
       обходЛКП ( Left ( b ) );                обходЛПК ( Left ( b ) );
       посетить ( Root ( b ) );                обходЛПК ( Right ( b ) );
       обходЛКП ( Right ( b ) );               посетить ( Root ( b ) );
    end                                   end
  end{обходЛКП};                          end{обходЛПК}

   Следует обратить внимание на то, что в литературе используются различ-
ная терминология при именовании видов обхода бинарного дерева. Перечис-
лим наиболее популярные варианты терминологии (виды обходов перечисле-
ны во всех вариантах в одном и том же порядке):
   1) КЛП, ЛКП, ЛПК [14];
   2) прямой, обратный, концевой [10];
   3) прямой, симметричный, обратный [13];
   4) сверху вниз, слева направо, снизу вверх [5,6];
   5) префиксный (PreOrder), инфиксный (InOrder), постфиксный
   (PreOrder) [5,6].
   Иногда обход КЛП называют обходом в глубину. В некоторых случаях
используется смешанная терминология [16]. Будем придерживаться далее

                                     50