ВУЗ:
Составители:
74
При обработке древовидных структур наиболее типичной является опе-
рация обхода − процедура, при выполнении которой каждый узел обрабатыва-
ется только один раз. Произвольное бинарное дерево можно обрабатывать с
помощью нисходящего (от корня вниз к листьям), восходящего (от листьев
вверх к корню) и смешанного (от самого левого листа через корень к
самому
правому листу) обходов.
Нисходящий обход. Первым читается корень, затем узлы в на-
правлении вниз и влево. Если пути влево нет, то движение идет по ближайшему
правому пути. При рассмотрении очередного узла просматриваются слева на-
право исходящие из него ветви. Так, для произвольного двоичного дерева, изо-
браженного на рис. 5.24, при нисходящем
обходе вершины дерева будут чи-
таться в таком порядке: 21, 7, 6, 19, 17, 13, 18, 20, 33, 38, 100, 63, 51, 260, 180.
Рис. 5.24. Двоичное дерево
Восходящий обход. Чтение начинается с левого листа. Каждый
узел читается после того, как прочитаны его левый и правый порожденные уз-
лы. Для дерева, изображенного на рис. 5.16, порядок чтения вершин следую-
щий: 6, 13, 18, 17, 20, 19, 7, 51, 63, 180, 260, 100, 38, 33, 21.
Смешанный
обход. Первым читается левый лист, затем следуют
последовательные подъемы и спуски. Каждый узел читается лишь тогда, когда
его левое поддерево полностью обойдено, после чего обходится правое подде-
рево. Узлы дерева, изображенного на рис. 45, будут читаться в следующем по-
рядке: 6, 7, 13, 17, 18, 19, 20, 21, 33, 38, 51, 63, 100, 180, 260. Нетрудно заметить,
что при смешанном обходе получается последовательность, упорядоченная по
возрастанию ключей
.
Оптимальный обход определяется типом конкретной задачи. Например,
смешанный обход используется для вычисления функций, заданных на опреде-
ленных вершинах дерева (см. рис. 5.11), а также для упорядочения массивов
данных. Восходящий и нисходящий обходы используются в трансляторах опе-
13
18
17
20
51
63
260
19
7
180
100
38
33
21
6
Страницы
- « первая
- ‹ предыдущая
- …
- 72
- 73
- 74
- 75
- 76
- …
- следующая ›
- последняя »
