Содержание
9
ОСНОВЫ АЛГОРИТМОВ И СТРУКТУР ДАННЫХ
Таблица 4
1
2
3
4
5
6
7
8
9
10
11
12
13
6
2
7
1
3
8
λ
λ
λ
4
5
λ
Λ
… …
2.1. Прохождение деревьев
Любой алгоритм, оперирующий с данными, явно или не явно
организованными в виде дерева совершает обход вершин этого дерева, начиная
с корня в некотором порядке.
Порядок, в котором получается результат, позволяет разделить алгоритмы
обработки деревьев на три вида.
1. Прохождение в глубину (или прохождение в прямом порядке).
Определяется следующей процедурой:
Первый шаг
: получение корня.
Следующие шаги
: прохождение в глубину последовательно всех
поддеревьев.
A
B
C
D
E
F
G
H
I
J
K
L
Рис. 4. Дерево
Для дерева на Рис. 4 прохождение в глубину даёт следующий порядок
обработки:
A B C D E F G H I J K L
2. Прохождение в глубину в обратном порядке.
Начальные шаги
:
пройти
в глубину (последовательно) все поддеревья.
Последний шаг
: посетить корень.
B D E F C G J K I L H A
1...,2,3,4,5,6,7,8,9,10 12,13,14,15,16,17,18,19,20,21,...106