2015-04-08
769
В ходе решения прикладных задач с применением структур в виде деревьев очень часто выполняются различные обходы дерева. Существует несколько способов обхода (прохождения) всех узлов дерева. Наиболее популярны три следующих способа обхода дерева: прямой (сверху вниз), обратный (снизу вверх), слева направо (симметричный).
Все три способа обхода дерева можно определить рекурсивно следующим образом.
Если дерево Т является нулевым деревом, то в список обхода заносится пустая запись.
Если дерево Т состоит из одного узла, то в список обхода записывается этот узел.
Далее, пусть Т – дерево с корнем n и поддеревьями 
, тогда для различных способов обхода имеем следующее:
а) при прохождении в прямом порядке (т.е. при прямом упорядочивании) узлов дерева Т сначала посещается корень n, а затем узлы поддерева 
далее все узлы поддерева 
и т. д. Последним посещаются узлы поддерева 
б) при симметричном обходе узлов дерева Т сначала посещаются в симметричном порядке все узлы поддерева 
далее корень n, затем последовательно в симметричном порядке все узлы поддеревьев 
.
в) в случае обхода в обратном порядке сначала посещаются в обратном порядке все узлы поддерева 
, затем последовательно посещаются все узлы поддеревьев , также в обратном порядке, последним посещается корень n.
Для бинарного дерева, изображенного на рис. 5.1, рассмотрим рекурсивные процедуры, реализующие три способа обхода дерева.
После каждой процедуры приводится последовательность узлов дерева, выделенная жирным шрифтом, соответствующая указанному способу обхода. Подчеркиванием помечены узлы, в которые возвращается процедура в ходе рекурсивного вычислительного процесса.
Рис. 5.1 Дерево обхода
Прямой обход дерева:
Procedure prym_print(var x:pt);
Begin
if x<> nil then
Begin
write (x^.data);
prym_print(x^.left);
prym_print(x^.right);
End;
End;
Последовательность обработки: 1, 2, 3, 2, 4, 2, 1, 5, 6, 5, 7, 5, 1
Симметричный обход дерева:
Procedure sim_print(var x:pt);
Begin
if x<> nil then
Begin
sim_print(x^.left);
write (x^.data);
sim_print(x^.right);
End;
nd;
Последовательность обработки: 1, 2, 3, 2, 4, 2, 1, 5, 6, 5, 7, 5, 1
Обратный обход дерева:
Procedure obr_print(var x:pt);
Begin
if x<> nil then
Begin
obr_print(x^.left);
obr_print(x^.right);
write (x^.data);
End;
End;
Последовательность обработки: 1, 2, 3, 2, 4, 2, 1, 5, 6, 5, 7, 5, 1
