ВУЗ:
Составители:
Рубрика:
36
К Д
1
Д
2
... Д
n
Для бинарного дерева. Корень, левое поддерево в префиксном порядке,
правое поддерево в префиксном порядке:
+ a * b c
3) Постфиксный порядок обхода.
Для произвольного дерева. Вначале обходятся все поддеревья в постфикс-
ном порядке, потом корень:
Д
1
Д
2
... Д
n
К
Для бинарного дерева. Левое поддерево в постфиксном порядке, правое
поддерево в постфиксном порядке, корень:
a b c * +
Отметим, что порядок обхода бинарного дерева разбора выражения соответ-
ствует форме записи этого выражения: при инфиксном обходе дерева получаем
инфиксную форму, при префиксном – префиксную, при постфиксном – пост-
фиксную.
Имеется несколько важных классов бинарных деревьев. Бинарное
дерево на-
зывается идеально сбалансированным, если для каждого его узла количество уз-
лов в левом и правом поддеревьях отличается максимум на единицу. Бинарное
дерево называется полным, если все его уровни полностью заполнены. Нетрудно
подсчитать, что количество узлов в полном бинарном дереве глубины k составля-
ет
12
1
−
+k
.
Приведем примеры идеально сбалансированных деревьев:
Из них полными являются первое, третье и последнее.
Для создания бинарного дерева в программе нам потребуется следующая
структура, определяющая узел дерева:
type
PNode=^TNode;
TNode=record
data: DataType;
left,right: PNode;
end;
Здесь left и right – указатели на левое и правое поддерево, DataType – опи-
санный ранее тип, для которого определены операции сравнения =, >, <. Нам по-
требуется также
функция NewNode, возвращающая узел дерева с заполненными
полями:
Страницы
- « первая
- ‹ предыдущая
- …
- 32
- 33
- 34
- 35
- 36
- …
- следующая ›
- последняя »
