Комбинаторные алгоритмы для программистов



             

Прохождения


Во многих приложениях необходимо пройти лес, заходя в узлы, то есть обрабатывая их некоторым систематическим образом. Посещение каждого узла может быть связано с простой операцией, такой как печать содержимого, или со сложной, такой как вычисление функции. Будем предполагать, что при посещении узла структура леса не меняется. Рассмотрим четыре основных способа прохождения леса: в глубину, снизу вверх, в горизонтальном порядке и для бинарных деревьев - в симметричном порядке.

При прохождении в глубину, известном также как прохождение в прямом порядке, узлы леса проходятся в соответствии со следующей рекурсивной процедурой:

  1. Посетить корень первого дерева.
  2. пройти в глубину поддерева первого дерева (если оно есть).
  3. Пройти в глубину оставшиеся деревья, если они есть.

Например, для леса, показанного на рис. 4.7, узлы будут проходиться в следующем порядке:

A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S.

Лес

Рис. 4.7.  Лес

Название "в глубину" отражает тот факт, что после посещения некоторого узла мы продолжаем прохождение в глубь дерева всякий раз, когда это возможно. Такой порядок особенно полезен в процедурах поиска.

Для бинарных деревьев эта процедура упрощается и выглядит следующим образом.

  1. Посетить корень.
  2. Пройти в глубину левое поддерево
  3. Пройти в глубину правое поддерево.

Прохождение снизу вверх, известное также как обратный порядок или концевой порядок, осуществляется согласно следующей рекурсивной процедуре:

  • Пройти снизу вверх поддеревья первого дерева, если они есть.
  • Посетить корень первого дерева.
  • Пройти снизу вверх оставшиеся деревья, если они есть.

Название "снизу вверх" связано с тем, что в момент посещения произвольного узла его потомки оказываются уже пройденными. Такой порядок прохождения полезен, в частности, потому, что он позволяет вычислять рекурсивно определенные функции на лесах. При этом порядке прохождения узлы леса, показанного на рис. 4.7, проходятся в такой последовательности:

B,D,E,F,C,G,J,K,I,L,H,A,O,P,N,R,Q,S,M
. Рекурсивная процедура прохождения снизу вверх применительно к бинарным деревьям имеет следующий вид:




Содержание  Назад  Вперед