Обходы дерева

Существует несколько способов обхода всех узлов дерева. Три наиболее часто используемых способа обхода называются прямой, обратный и симметричный обходы

Обход в глубину «сверху вниз»: название имеет смысл лишь в случае стандартного расположения дерева корнем кверху.

Алгоритм обхода

- Начать с корня дерева.

- Пометить текущую вершину.

- Совершить прямой обход левого поддерева.

- Совершить прямой обход правого поддерева.

Обходы- прямой, обратный и симметричный обходы можно рекурсивно определить следующим образом:

Если дерево T является нулевым деревом, то в список обхода записывается пустая строка.

Если дерево T состоит из одного узла, то в список обхода записывается этот узел;

Пусть дерево T имеет корень n и поддеревья T 1, T 2,... T m, как показано на рисунке

 

 

Тогда для различных способов обхода имеем следующее:

Прямой обход.

Сначала посещается корень n, затем в прямом порядке узлы поддерева T 1, далее все узлы поддерева T 2 и т.д. Последними посещаются в прямом порядке узлы поддерева T m.

Обратный обход.

Сначала посещаются в обратном порядке все узлы поддерева T 1, затем в обратном порядке узлы поддеревьев T 2 … T m, последним посещается корень n.

Симметричный обход.

Сначала в симметричном порядке посещаются все узлы поддерева T 1, затем корень n, после чего в симметричном порядке все узлы поддеревьев T 2 … T m.

Рассмотрим пример всех способов обхода дерева, изображенного на рисунке:

 

Порядок узлов данного дерева в случае прямого обхода будет следующим:

1 2 3 5 8 9 6 10 4 7.

Обратный обход этого же дерева даст нам следующий порядок узлов:

2 8 9 5 10 6 3 7 4 1.

При симметричном обходе мы получим следующую последовательность узлов:

2 1 8 5 9 3 10 6 7 4.