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

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

При обходе в ширину узлы посещаются уровень за уровнем(N-й уровень дерева - множество узлов с высотой N). Каждый уровень обходится слева направо. Для дерева изображенного на рисунке 1.2 обход в ширину представляет последовательность вершин:

A- B –C – D – E – F – K - G

И графически (рисунок 2.4):

Заметим, что перечисление узлов происходит в порядке удаления от корня, что делает поиск в ширину удобным, например, для поиска узла дерева со значением k, наиболее близкого к корню, и т.д.

Для реализации используется структура queue - очередь с методами

enqueue - поставить в очередь

dequeue - взять из очереди

empty - возвращает TRUE, если очередь пуста, иначе – FALSE.

И часть программного кода для данного обхода будет соответственно иметь вид:

/*ОБХОД В ШИРИНУ*/

q.enqueue(root); // корень в очередь

while (! q.empty) {

der = q.dequeue();

visit der; // посетить der

if (! der.left.empty) // der.left - левое поддерево

q.enqueue(der.left);

if (! der.right.empty) // der.right - правое поддерево

q.enqueue(der.right);}

Дата добавления: 2015-07-26; просмотров: 415; Нарушение авторских прав

Мы поможем в написании ваших работ!