дерева, приведенного на рис. 4.19, длина внешнего пути ера 153.

гццсло специальных узлов т, которые нужно добавить дереву степени d, непосредственно зависит от числа п ис-* яяых узлов. Заметим, что на каждый узел указывает ровно лва ветвь. Следовательно, в расширенном поддереве имеется Z+n ветвей. С другой стороны, из каждого исходного узла додят d ветвей, а из специальных узлов - ни одной. По- тоМУ всего имеется dn + 1 ветвей (1 дает ветвь, указывающую на корень). Из этих двух формул мы получаем следующее равенство между числом т специальных узлов и п исходных узлов: dn + 1 = m + п, или

m = (d - l) -f 1. (4.36)

Максимальное число узлов в дереве заданной высоты h достигается в случае, когда все узлы имеют d поддеревьев, кроме узлов уровня h, не имеющих ни одного. Тогда в дереве степени d первый уровень содержит 1 узел (корень), уровень2 содержит d его потомков, уровень 3 содержит d потомков d узлов уровня 2 и т. д. Это дает следующую величину:

Na{h)=l+d + d+ ...+ d - = £ d (4.37)

в качестве максимального числа узлов для дерева с высотой h и степенью d. При d = 2 мы получаем

т> iV2(ft)==i;2 = 2-l. (4.38)

Упорядоченные деревья степени 2 играют особо важную роль. Они называются бинарными деревьями. Мы определяем упорядоченное бинарное дерево как конечное множество эле->№нтов {узлов), калсдый из которых либо пуст, либо состоит корня {узла), связанного с двумя различными бинарными ревьями, называемыми левым и правым поддеревом корня. следующих пунктах этого раздела мы будем рассматривать сключительно бинарные деревья и поэтому будем употреб- ть слово дерево , имея в виду упорядоченное бинарное Абрево . Деревья, имеющие степень больше 2, называются льно ветвящимися деревьями {multiway trees), они рассматриваются в разд. 5 этой главы.

Знакомыми примерами бинарных деревьев являются фа-Чльное (генеалогическое) дерево с отцом и матерью человека Качестве его потомков (!), история теннисного турнира, где является каждая игра, определяемая ее победителем, ДДеревьями - две предыдущие игры соперников; арифме-ское выражение с двухместными операциями, где каждая

Рис. 4.20. Выражение (a + blc)*(d - e*l), представленное в виде дерева.

с фиксированной структурой, т. е. фиксированного типа, где степень дерева определяет число компонент-ссылок, указывающих на поддеревья данного узла. Ясно, что ссылка на пустое поддерево обозначается через nil. Следовательно, дерево на рис. 4.20 состоит из компонент такого типа:

type node = record op: char,

left, right: t node (4.39)

и может строиться, как показано на рис. 4.21.

Ясно, что существуют способы представления абстрактной древовидной структуры в терминах других типов данных, например таких, как массив. Это - общепринятый способ в всех языках, где нет средств динамического размещения компонент и указания их с помощью ссылок. В этом случае Д^ рево на рис. 4.20 можно представить переменной-массИВОМ. описанной как

: array[l..ll] of

record op: char; ,

left, right: integer (4-4J)

и CO значениями компонент, приведенными в табл. 4.3.

операция представляет собой ветвящийся узел с операнда в качестве поддеревьев (см. рис. 4.20).

Теперь мы обратимся к проблеме представления деревь Ясно, что изображение таких рекурсивных структур (tohh* рекурсивно определенных. - Прим. ред.) с разветвлениям^ предполагает использование ссылок. Очевидно, что не имее смысла описывать переменные с фиксированной древовидно структурой, вместо этого узлы определяются как переменны

Хотя подразумевается, что массив f представляет абстракт-vio структуру дерева, мы будем называть его все же не дере-пМ. массивом согласно явному определению. Мы не будем

суждать другие возможные представления деревьев в си- - емах, где отсутствует динамическое распределение памяти.

Рис. 4.21. Дерево, представленное как структ)фа данных.

поскольку мы считаем, что системы программирования и язы- ки, имеющие это свойство, являются или станут щироко распространенными.

Таблица 4.3. Дерево, представленное с помощью массива

g прежде чем обсуждать, как лучще использовать деревья выполнять операции с деревьями, мы покажем на при-