Существует достаточно много алгоритмов работы с древовидными структурами, в которых часто встречается понятие обхода (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);
}

Рекурсивные обходы можно, очевидно, организовать и с помощью стека, 'развернув' рекурсию.