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