Обход бинарного дерева «в глубину» (в прямом порядке)

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

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

2. Пройти в прямом порядке левое поддерево.

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

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

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

Итеративный алгоритм прохождения БД «в глубину»:

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

2. Пройти корень T и включить его адрес в стек.

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

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

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

Обход бинарного дерева «в ширину» (по уровням)

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

В алгоритме обхода БД «в ширину» будем использовать очередь, в которую будут помещаться адреса вершин в порядке обхода.

Алгоритм прохождения БД «в ширину»:

1. Инициализировать очередь.

2. Занести адрес корня T в очередь.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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