Составители:
57
TTree = record
Data: TypeElement; {поле данных}
Childs, Next: PTree; {указатели на потомков и на следующий}
end;
1.3.4.2. Обходы деревьев
Существует несколько способов обхода (просмотра) всех вершин дере-
ва. Три наиболее часто используемых способа обхода называются (рис. 15):
– в прямом порядке;
– в обратном порядке;
– в симметричном (внутреннем) порядке.
Все три способа обхода рекурсивно можно определить следующим
образом:
1) если дерево Tree является пустым деревом, то в список обхода
заносится пустая запись;
2) если дерево Tree состоит из одной вершины, то в список обхода
записывается эта вершина;
3) если Tree – дерево с корнем n и поддеревьями Tree
1
, Tree
2
, …,
Tree
k
, то:
– при прохождении в прямом порядке сначала посещается корень n,
затем в прямом порядке вершины поддерева Tree
1
, далее в прямом по-
рядке вершины поддерева Tree
2
и т. д. Последними в прямом порядке
посещаются вершины поддерева Tree
k
;
– при прохождении в обратном порядке сначала посещаются в об-
ратном порядке вершины поддерева Tree
1
, далее последовательно в об-
ратном порядке посещаются вершины поддеревьев Tree
2
, …, Tree
k
. Пос-
ледним посещается корень n;
Прямой
a
b
c
d e
f
a b d e c f
Симметричный
d b e a c f
a
b
c
d e f
d e b f c a
Обратный
a
b
c
d e f
Рис. 15. Обходы деревьев
Страницы
- « первая
- ‹ предыдущая
- …
- 55
- 56
- 57
- 58
- 59
- …
- следующая ›
- последняя »
