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

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

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

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

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

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

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

посетить корень	левое поддерево	левое поддерево
левое поддерево	посетить корень	правое поддерево
правое поддерево	правое поддерево	посетить корень

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

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

. Такое прохождение дерева полезно в определенных алгоритмах на графах.

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

---

---

---