Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Существует достаточно много алгоритмов работы с древовидными структурами, в которых часто встречается понятие обхода (traversing) дерева или "прохода" по дереву. При таком методе исследования дерева каждый узел посещается только один раз, а полный обход задает линейное упорядочивание узлов, что позволяет упростить алгоритм, так как при этом можно использовать понятие "следующий" узел. т.е. узел стоящий после данного при выбранном порядке обхода.
Существует несколько принципиально разных способов обхода дерева:
Обход в прямом порядке
Каждый узел посещается до того, как посещены его потомки.
Для корня дерева рекурсивно вызывается следующая процедура:
Посетить узел
Обойти левое поддерево
Обойти правое поддерево
Примеры использования обхода:
Симметричный обход
Посещаем сначало левое поддерево, затем узел, затем - правое поддерево.
Для корня дерева рекурсивно вызывается следующая процедура:
Обойти левое поддерево
Посетить узел
Обойти правое поддерево
Обход в обратном порядке
Узлы посещаются 'снизу вверх'.
Для корня дерева рекурсивно вызывается следующая процедура:
Обойти левое поддерево
Обойти правое поддерево
Посетить узел
Примеры использования обхода:
Обход в ширину
При обходе в ширину узлы посещаются уровень за уровнем(N-й уровень дерева - множество узлов с высотой N). Каждый уровень обходится слева направо.
Для реализации используется структура queue - очередь с методами
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);
}