Обход бинарного дерева в симметричном порядке

Для прохождения БД в симметричном порядке нужно выполнить следующие действия:

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

2. Попасть в корень.

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

Выполнив обход в симметричном порядке БД на рис.21, получим последовательность: DCEBFAGIHJ.

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

Итеративный алгоритм прохождения БД в симметричном порядке:

1. Инициализировать стек.

2. Адрес корня T включить в стек.

3. Если стек пуст, то перейти к п.5. Если есть левый сын вершины T, то занести его адрес в стек, иначе извлечь из стека адрес вершины Т, пройти ее и если у нее есть правый сын, то занести его в стек.

4. Перейти к п.3.

5. Конец алгоритма.

Обход бинарного дерева в обратном порядке

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

1. Пройти в обратном порядке левое поддерево.

2. Пройти в обратном порядке правое поддерево.

3. Попасть в корень.

Это рекурсивный алгоритм, т.к. поддеревья обрабатываются точно так же, как и БД. Нерекурсивный выход произойдет при достижении пустого дерева. Применив алгоритм к БД на рис.21, получим последовательность: DECFBIJHGA.