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



             

Прохождения - часть 2


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

Симметричный порядок для бинарных деревьев определяется рекурсивно следующим образом:

  1. Пройти в симметричном порядке левое поддерево.
  2. Посетить корень.
  3. Пройти в симметричном порядке правое поддерево.

Такой способ прохождения известен также как лексикографический порядок или внутренний порядок. Заметим, что прохождение леса снизу вверх эквивалентно прохождению в симметричном порядке бинарного дерева, соответствующего этому лесу (при естественном соответствии).

Сравнивая рекурсивные процедуры прохождения бинарных деревьев в глубину, снизу вверх и в симметричном порядке, можно обнаружить их значительное сходство:

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

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

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

A,M,B,C,G,H,N,Q,S,D,E,F,I,L,O,P,R,J,K
. Такое прохождение дерева полезно в определенных алгоритмах на графах.




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