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

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

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

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

Если дерево Т состоит из одного узла, то в список обхода записывается этот узел.

Далее, пусть Т – дерево с корнем n и поддеревьями , тогда для различных способов обхода имеем следующее:

а) при прохождении в прямом порядке (т.е. при прямом упорядочивании) узлов дерева Т сначала посещается корень n, а затем узлы поддерева далее все узлы поддерева и т. д. Последним посещаются узлы поддерева

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

в) в случае обхода в обратном порядке сначала посещаются в обратном порядке все узлы поддерева , затем последовательно посещаются все узлы поддеревьев , также в обратном порядке, последним посещается корень n.

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

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

Рис. 15 – Дерево обхода

Прямой обход дерева:

Procedure СверхуВниз (t: АдрЭлем);

begin

if t <>nil

then begin

P(t); {обработка вершины}

write(t);

СверхуВниз (t^.left);

СверхуВниз (t^. right);

end

end;

Последовательность обработки: 1, 2, 3, 2, 4, 2, 1, 5, 6, 5, 7, 5, 1

Симметричный обход дерева:

Procedure СлеваНаправо (t: АдрЭлем);

begin

if t <>nil

then begin

СлеваНаправо (t^.left);

P(t); {обработка вершины}

write(t);

СлеваНаправо (t^. right);

end

end;

Последовательность обработки: 1, 2, 3, 2, 4, 2, 1, 5, 6, 5, 7, 5, 1

Обратный обход дерева:

Procedure СнизуВверх (t: АдрЭлем);

begin

if t <>nil

then begin

СнизуВверх (t^.left);

СнизуВверх (t^. right);

P(t); {обработка вершины}

write(t);

end

end;

Последовательность обработки: 1, 2, 3, 2, 4, 2, 1, 5, 6, 5, 7, 5, 1

Дата добавления: 2015-07-16