Обратный метод прохождения дерева

При обратном прохождении посещение узла откладывается до тех пор, пока не будут рекурсивно пройдены оба его поддерева. Порядок операций дает так называемое LRN (left, right, node) сканирование.

1) прохождение левого поддерева.

2) прохождение правого поддерева.

3) посещение узла.

При обратном прохождении дерева Tree_0 узлы посещаются в порядке D B E C A.

Функция сканирует дерево снизу вверх. Мы спускаемся вниз по левому дереву [t->Left()], а затем вниз по правому [t->Right()]. Последней операцией является посещение узла.

//Обратное рекурсивное прохождение узлов дерева

template <class T>

void Postorder (TreeNode<T> *t, void visit (T& item))

{

//Рекурсивное прохождение завершается на пустом поддереве

if (t != NULL)

{

//Спуститься по левому поддереву

Postorder(t->Left(), visit);

//Спуститься по правому поддереву

Postorder(t->Right(), visit);

//Посетить узел

visit(t->data);

}

}

Прямой метод прохождения определяется посещением узла в первую очередь и последующим прохождением сначала левого, а потом правого его поддеревьев (NLR).

Ясно, что префиксы pre, in и post в названиях функций показывают, когда происходит посещение узла. В каждом случае сначала осуществлялось прохождение по левому поддереву, а уже потом по правому. Фактически существуют еще три алгоритма, которые выбирают сначала правое поддерево и потом левое. Алгоритмы прохождения посещают каждый узел дерева. Они дают эквивалент последовательного сканирования массива или связанного списка.

Покажем на примере результаты использования различных методов прохождения. Для изображенного на Рис. 9 дерева Tree_2 имеет место следующий порядок посещения узлов.

Прямой: A B D G C E H I F

Симметричный: D G B A H E I C F

Обратный: G D B H I E F C A