Алгоритм SyntOrder

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

Синтаксический обход

Обратный обход произвольного связного графа

Реализация

procedure postorder(p:ukaz; k:integer);begin if p^.left<>nil then postorder(p^.left,k+1); if p^.right<>nil then postorder(p^.right,k+1) p^.mark:=k;end; begin... postorder(root,1); {Вызов из тела программы}...end.

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

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

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

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

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

Замечание: Этот обход специфичен только для бинарных деревьев, поэтому невозможно применить его к произвольному графу, каркасом которого совершенно не обязательно будет именно бинарное дерево.

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