ГоловнаЗворотній зв'язок
Главная->Математика і інформатика->Содержание->Прямой, обратный и симметричный обходы дерева

Алгоритмы структуры данных

Прямой, обратный и симметричный обходы дерева

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

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

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

• Далее, пусть Т — дерево с корнем п и поддеревьями Т1, Т2, ..., Tk, как показано на рис. 3.4. Тогда для различных способов обхода имеем следующее.

 

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

2.    При симметричном обходе узлов дерева Т сначала посещаются в симметричном порядке все узлы поддерева Т1, далее корень п, затем последовательно в симметричном порядке все узлы поддеревьев Т2, …, Tk.

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

В листинге 3.1,а показан набросок процедуры PREORDER (Прямое упорядочивание), составляющей список узлов дерева при обходе его в прямом порядке. Чтобы из этой процедуры сделать процедуру, выполняющую обход дерева в обратном порядке, надо просто поменять местами строки (1) и (2). В листинге 3.1,6 представлен набросок процедуры INORDER (Внутреннее упорядочивание). В этих процедурах производится соответствующее упорядочивание деревьев путем вызова соответствующих процедур к корню дерева.

 

32