Алгоритм 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. Последовательность нумерации вершин при обратном обходе дерева