Структуры и алгоритмы обработки данных

       

Прохождение бинарных деревьев


В зависимости от  последовательности обхода поддеревьев различают три вида обхода (прохождения) деревьев (рис.4.9):

1. Сверху вниз А, В, С.

2. Слева направо или симметричное прохождение В, А, С.

3. Снизу вверх В, С, А.

Наиболее часто применяется второй способ.

Ниже приведены рекурсивные алгоритмы прохождения бинарных деревьев.

subroutine pretrave (tree) ‘сверху вниз

if tree <> nil then

  print info(tree)

  pretrave(left(tree))

  pretrave(right(tree))



endif

return

subroutine intrave (tree) ‘симметричный

if tree <> nil then

  intrave(left(tree))

  print info(tree)

  intrave(right(tree))

endif

return

Procedure pretrave (tree: tnode)

Begin

  if tree <> nil then

    begin

      WriteLn(Tree^.Info);

      Pretrave(Tree^.left);

      Pretrave(Tree^.right);

     End;

end;

procedure intrave (tree: tnode)

begin

  if tree <> nil then

    begin

      intrave(Tree^.left);

      writeLn(Tree^.info);

       intrave(Tree^.right);

     end;

end;

Поясним подробнее рекурсию алгоритма обхода дерева слева направо.

Пронумеруем строки алгоритма

intrave (tree):

 

1                   if tree <> nil

2                      then intrave (left(tree))

3                            print info (tree)

4                           intrave (right (tree))

5                      endif

6                   return

Обозначим указатели: t > tree;  l >

left;  r > right

На приведенном рис. 4.11 проиллюстрирована последовательность вызова процедуры intrave (tree) по мере обхода узлов простейшего дерева, изображенного на рис. 4. 10.



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