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

Предзаказ Траверс

Предварительный заказ сначала посещает корневой узел, затем рекурсивно пересекает левое поддеревье, затем правое поддеревье. Этот метод полезен для копирования деревьев или создания префиксных выражений.

Например, если учесть дерево:

A
/
B C
/
D E F

Последовательность прохождения предзаказа: A, B, D, E, C, F.

Поперечный обход

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

Используя одно и то же дерево, последовательность обхода по порядку составляет: D, B, E, A, C, F.

Пост-заказ Траверс

Постпорядковый обход посещает левое поддеревье, затем правое поддеревье и, наконец, корневой узел. Такой подход полезен для удаления деревьев или оценки выражений постфикса.

Для примера дерева последовательность прохождения по последовательности последовательности последовательности последовательности последовательности последовательности последовательности последовательности: D, E, B, F, C, A.

Практические расчеты

Рассмотрим дерево:

1
/
2 3
/
4 5 6

Предзаказ на прохождение: 1, 2, 4, 5, 3, 6

Порядковый обход: 4, 2, 5, 1, 3, 6

Постпорядковый обход: 4, 5, 2, 6, 3, 1