Next:4.6
Обходы графа в глубину и ширину
Up:4
Разработка алгоритмов
Previous:4.4
Алгоритм поиска с возвращением
Рис. 20. Дерево
Существует три способа обхода ордерева в глубину, различающихся порядком
посещения вершины и ее сыновей При префиксном обходе ордерева ,
сначала нужно посетить его корень
,
а затем, если
не является листом, то для реализовать префиксный обход всех ее поддеревьев
в порядке их упорядоченности. Например, для дерева, показанного на рис.
20, вершины будут проходиться в следующем порядке:
.
Следующая рекурсивная процедура реализует префиксный обход ордерева:
procedure ПРЕФИКСНЫЙ-ОБХОД(:
ордерево);
begin
Посетить корень
ордерева
;
if
не лист then
Пусть
-- поддеревья корня
;
for i := 1 to
k do ПРЕФИКСНЫЙ-ОБХОД()
end
end
end.
Если использовать стек
для хранения текущего пути по дереву, т.е. пути, который начинается в корне
дерева и кончается в вершине, посещаемой в данный момент, то можно предложить
следующий нерекурсивный алгоритм префиксного обхода ордерева:
Посетить корень дерева и поместить его в пустой стек ;
while стек
не является пустым do
Пусть
-- вершина, находящаяся на верху стека
;
if Сыновья вершины
еще не посещались
then Посетить старшего сына вершины
и поместить его в стек
else
Удалить
вершину
из стека S;
if
имеет братьев then Посетить брата вершины
и поместить его в стек
end
end
end
Аналогичные алгоритмы можно использовать для двух других способа обхода ордерева в глубину: постфиксного и инфиксного.
Способ обхода ордерева в ширину предполагает посещение вершин
ордерева по старшинству, уровень за уровнем, отправляясь от корня. Например,
при обходе в ширину изображенного на рис. 20 дерева вершины проходятся
сверху вниз и слева направо и посещаются в следующем порядке: .
Приведенный ниже алгоритм реализует обход дерева в ширину, используя очередь
О.
Поместить корень в пустую очередь O;
while очередь O не пуста do
Пусть
-- первая вершина очереди O;
Посетить вершину
и удалить ее из O;
Поместить всех сыновей вершины
в очередь O, начиная со старшего сына
end
Следует заметить, что обход дерева поиска в ширину позволяет обходить
дерево поиска одновременно с его построением. Таким образом, можно решать
задачу нахождения какого-нибудь одного решения в форме вектора
неизвестной длины (не зная
),
если только известно, что существует конечное решение задачи.
Next:4.6
Обходы графа в глубину и ширину
Up:4
Разработка алгоритмов
Previous:4.4
Алгоритм поиска с возвращением