Алгоритм PostOrder

Другие названия

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

Прямой обход произвольного связного графа

Для простоты изложения будем считать, что граф задан матрицей смежности, которая хранится в квадратном массиве sm. Дополнительный линейный массив mark хранит информацию о последовательности посещения вершин:

procedure preorder_graph(v: byte);var i: byte;begin k:= k+1; mark[v]:= k; {текущей вершине v присвоен порядковый номер} for i:= 1 to n do if (mark[i]=0)and(sm[v,i]=1) {есть ребро из текущей вершины v в еще не помеченную вершину i} then preorder_graph(i);end; begin... k:= 0; preorder_graph(start); {Вызов из тела программы}...end.

Постфиксный обход: результатом обратного обхода ДСА арифметического выражения будет постфиксный вариант записи этого выражения.

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

1. Начать с корня дерева.
2. Совершить обратный обход левого поддерева.
3. Совершить обратный обход правого поддерева.
4. Пометить текущую вершину.

Замечание: Этот алгоритм также может быть распространен на случай произвольного корневого дерева.

Рис. 12.3. Последовательность нумерации вершин при обратном обходе дерева

Дата добавления: 2014-01-03