ВУЗ:
Составители:
Рубрика:
35
Пример 3. Дерево разбора выражения a+b*c.
Дерево, приведенное в примере 3, является бинарным, поскольку операции +
и * – бинарные. Каждый узел этого дерева, не являющийся листом, содержит знак
операции, а два операнда данной операции являются сыновьями этого узла. Сын
является либо листом и тогда представляет переменную, либо корнем поддерева.
Например, сыновьями узла, содержащего операцию +, являются операнд a и опе-
ранд b*c,
который также представляется в виде дерева.
Из примеров мы видим, что деревья имеют рекурсивную природу. Действи-
тельно, любой узел дерева либо является листом, либо имеет сыновей, каждый из
которых является корнем поддерева. Приведем другое, рекурсивное определение
дерева:
Дерево ::= <пусто>
│ Корень СписокПоддеревьев
СписокПоддеревьев ::= <пусто>
│ Дерево СписокПоддеревьев
4.1 Порядки обхода деревьев
Как обойти дерево, посетив каждый его узел один раз?
Имеется несколько стандартных вариантов обхода деревьев. Все определения
будем давать для произвольного дерева, состоящего из корня К и n поддеревьев
n
ДДД ,...,,
21
, и для бинарного дерева, используя для иллюстрации дерево разбора
выражения a+b*c:
Заметим, что все порядки обхода формулируются как рекурсивные процедуры,
что отражает рекурсивность определения самого дерева.
1) Инфиксный порядок обхода.
Для произвольного дерева. Вначале обходится первое поддерево в инфикс-
ном порядке, затем корень и затем – остальные поддеревья в инфиксном порядке:
Д
1
K Д
2
... Д
n
Для бинарного дерева. Левое поддерево в инфиксном порядке, корень, пра-
вое поддерево в инфиксном порядке:
a + b * c
2) Префиксный порядок обхода.
Для произвольного дерева. Вначале обходится корень, а потом все подде-
ревья в префиксном порядке:
Страницы
- « первая
- ‹ предыдущая
- …
- 31
- 32
- 33
- 34
- 35
- …
- следующая ›
- последняя »
