Алгоритмы обхода бинарного дерева

 

Пусть в памяти ЭВМ находится БД. Задача обхода БД состоит в том, чтобы вывести информационную часть каждой вершины БД. Порядок прохождения вершин определяет алгоритм обхода БД. Рассмотрим некоторые алгоритмы обхода БД.

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

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

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. Конец алгоритма.