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

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

• в прямом порядке;

• в обратном порядке;

• в симметричном (внутреннем) порядке.

Все три способа обхода рекурсивно можно определить следующим образом:

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

2. Если дерево Tree состоит из одной вершины, то в список обхода записывается эта вершина;

3. Если Tree – дерево с корнем n и поддеревьями Tree₁, Tree₂, … Tree_k, то:

• при прохождении в прямом порядке сначала посещается корень n, затем в прямом порядке вершины поддерева Tree₁, далее в прямом порядке вершины поддерева Tree₂, и т.д. Последними в прямом порядке посещаются вершины поддерева Tree_k;

• при прохождении в обратном порядке сначала посещаются в обратном порядке вершины поддерева Tree₁, далее последовательно в обратном порядке посещаются вершины поддеревьев Tree₂, … Tree_k. Последним посещается корень n;

• при прохождении в симметричном порядке сначала посещаются в симметричном порядке вершины поддерева Tree₁, далее корень n, затем последовательно в симметричном порядке вершины поддеревьев Tree₂, … Tree_k.

Рисунок 3.10 – Порядки обхода дерева (прямой, симметричный, обратный)

Далее приведены макеты процедур, реализующих указанные способы обходов деревьев. При доработке представленного кода необходимо учитывать конкретную реализацию деревьев.

procedure PreOrder(n: вершина);

{Обход дерева в прямом порядке}

begin

Занести в список обхода вершину n;

for для каждого потомка s вершины n в порядке слева направо do

PreOrder(s);

end;

procedure InOrder(n: вершина);

{Обход дерева в симметричном порядке}

begin

if n – лист then begin

занести в список обхода узел n;

end else begin

InOrder(самый левый потомок вершины n);

Занести в список обхода вершину n;

for для каждого потомка s вершины n, исключая самый левый,

в порядке слева направо do

InOrder(s);

end;

end;

procedure PostOrder(n: вершина);

{Обход дерева в обратном порядке}

begin

for для каждого потомка s вершины n в порядке слева направо do

PostOrder(s);

Занести в список обхода вершину n;

end;

Листинг 3.21 – Обходы деревьев (PreOrder, InOrder, PostOrder)