Существует достаточно много алгоритмов работы с древовидными структурами, в которых часто встречается понятие обхода (traversing) дерева или "прохода" по дереву. При таком методе исследования дерева каждый узел посещается только один раз, а полный обход задает линейное упорядочивание узлов, что позволяет упростить алгоритм, так как при этом можно использовать понятие "следующий" узел. т.е. узел стоящий после данного при выбранном порядке обхода.
Существует несколько принципиально разных способов обхода дерева:
Обход в прямом порядке
Каждый узел посещается до того, как посещены его потомки.
Для корня дерева рекурсивно вызывается следующая процедура:
Посетить узел
Обойти левое поддерево
Обойти правое поддерево
Примеры использования обхода:
- решение задачи методом деления на части
- разузлование сверху
- стратегия "разделяй и властвуй" (Сортировка Фон Hеймана, быстрая сортировка, одновременное нахождение максимума и минимума последовательности чисел, умножение длинных чисел).
Симметричный обход
Посещаем сначало левое поддерево, затем узел, затем - правое поддерево.
Для корня дерева рекурсивно вызывается следующая процедура:
Обойти левое поддерево
Посетить узел
Обойти правое поддерево
Обход в обратном порядке
Узлы посещаются 'снизу вверх'.
Для корня дерева рекурсивно вызывается следующая процедура:
Обойти левое поддерево
Обойти правое поддерево
Посетить узел
Примеры использования обхода:
- анализ игр с полной информацией
- разузлование снизу
- динамическое программирование
Обход в ширину
При обходе в ширину узлы посещаются уровень за уровнем(N-й уровень дерева - множество узлов с
высотой N). Каждый уровень обходится слева направо.
Для реализации используется структура queue - очередь с методами
- enqueue - поставить в очередь
- dequeue - взять из очереди
- empty - возвращает TRUE, если очередь пуста, иначе - FALSE
q.enqueue(root); // корень в очередь
while (! q.empty) {
x = q.dequeue();
visit x; // посетить x
if (! x.left.empty) // x.left - левое поддерево
q.enqueue(x.left);
if (! x.right.empty) // x.right - правое поддерево
q.enqueue(x.right);
}
Рекурсивные обходы можно, очевидно, организовать и с помощью стека, 'развернув' рекурсию.
Обсудить на форуме »
|
