Обходы ордерева в глубину и в ширину

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

Рис. 20. Дерево

При префиксном обходе ордерева T, сначала нужно посетить его корень v, а затем, если v не является листом, то реализовать префиксный обход всех ее поддеревьев в порядке их упорядоченности. Например, для дерева, показанного на рис. 20, вершины будут проходиться в следующем порядке: A,B,C,D,E,F,G,H,I,J,K,L. Следующая рекурсивная процедура реализует префиксный обход ордерева:

procedure ПРЕФИКСНЫЙ-ОБХОД(T: ордерево);
begin
Посетить корень v ордерева T;
if v не лист then Пусть T₁,…,T_k – поддеревья корня v;
for i:= 1 to k do ПРЕФИКСНЫЙ-ОБХОД(T_i) end
end
end.

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

Посетить корень дерева и поместить его в пустой стек S;
while стек S не является пустым do
Пусть p – вершина, находящаяся на верху стека S;
if Сыновья вершины p еще не посещались
then Посетить старшего сына вершины p и поместить его в стек S
else Удалить вершину p из стека S;
if p имеет братьев then Посетить брата вершины p и поместить его в стек S end
end
end

Способ обхода ордерева в ширину предполагает посещение вершин ордерева по старшинству, уровень за уровнем, отправляясь от корня. Например, при обходе в ширину изображенного на рис. 20 дерева вершины проходятся сверху вниз и слева направо и посещаются в следующем порядке: A,B,C,G,H,D,E,F,I,L,J,K. Приведенный ниже алгоритм реализует обход дерева в ширину, используя очередь О.

Поместить корень в пустую очередь O;
while очередь O не пуста do
Пусть p – первая вершина очереди O;
Посетить вершину p и удалить ее из O;
Поместить всех сыновей вершины p в очередь O, начиная со старшего сына
end

Следует заметить, что обход дерева поиска в ширину позволяет обходить дерево поиска одновременно с его построением. Таким образом, можно решать задачу нахождения какого-нибудь одного решения в форме вектора (а₁, а₂,…) неизвестной длины (не зная r), если только известно, что существует конечное решение задачи.

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