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

Процедуры "обхода" дерева


Пусть задано бинарное дерево :

Существуют три принципа обхода бинарных деревьев. Рассмотрим их на примере заданного дерева :

1) Обход сверху вниз (корень посещается ранее, чем поддеревья) : A, B, C ;

2) Слева направо : B, A, C ;

3) Снизу вверх (корень посещается после поддеревьев) : B, C, A .

Наиболее часто применяется 2-ой способ, узлы посещаются в порядке возрастания значения их ключа.

Рекурсивные процедуры обхода дерева :

1) PROCEDURE pretrave (tree)

         IF tree<>nil

           THEN PRINT info (tree)

                     pretrave (left (tree))

                     pretrave (right (tree))



         END IF

      RETURN

2) PROCEDURE intrave (tree)

         IF tree<>nil

           THEN intrave (left (tree))

                      PRINT info (tree)

                      intrave (right (tree))

         END IF

         RETURN

3) PROCEDURE postrave (tree)

         IF tree<>nil

           THEN postrave (left (tree))

                      postrave (right (tree))

                      PRINT info (tree)

         END IF

         RETURN



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