2) узел типа Т, с которым связано конечное число древови ных структур с базовым типом Т, называемых подд ревьями.

Из сходства рекурсивных определений последовательц стей и древовидных структур видно, что последовательносх (список) есть древовидная структура, у которой каждый у^ имеет не более одного поддерева . Поэтому последователе ность (список) называется также вырожденным деревом.

Существует несколько способов изображения Древовидно структуры. Например, пусть базовый тип Т есть множество букв; такая древовидная структура разными способами изо-бражена на рис. 4.17. Все эти представления демонстрируй одну и ту же структуру и поэтому эквивалентны. С помощью графа можно наглядно представить разветвляющиеся связи которые по понятным причинам привели к общеупотребительному термину дерево . Однако довольно странно, что де-ревья принято рисовать перевернутыми или - если кто-то предпочитает иначе выразить этот факт - изображать корни дерева. Но последняя формулировка вводит в заблуждение, так как верхний узел (Л) обычно называют корнем. Хотя мы сознаем, что в природе деревья представляют собой несколько более сложные образования, чем нащи абстракции, мы будем в дальнейщем древовидные структуры называть просто деревьями.

Упорядоченное дерево - это дерево, у которого ветви каждого узла упорядоченны. Следовательно, два упорядоченных дерева на рис. 4.18 - это особые, отличные друг от друга деревья. Узел у, который находится непосредственно под узлом X, называется (непосредственным) потомком х; если-с находится на уровне i, то говорят, что у - на уровне i-f- Наоборот, узел х называется (непосредственным) предком и-Считается, что корень дерева расположен на уровне 1. Максимальный уровень какого-либо элемента дерева называется его глубиной или высотой.

Если элемент не имеет потомков, он называется тер0 нальным элементом или листом, а элемент, не являюшийс терминальным, называется внутренним узлом. Число (непо средственных) потомков внутреннего узла называется ег степенью. Максимальная степень всех узлов есть степень рева. Число ветвей, или ребер, которые нужно пройти, чтоб продвинуться от корня к узлу X, называется длиной пути Корень имеет длину пути 1, его непосредственные потомки' длину пути 2 и т. д. Вообще, узел на уровне / имеет Д^и * пути i. Длина пути дерева определяется как сумма длин тей всех его узлов. Она также называется длиной внугр него пути. Например, длина внутреннего пути дерева, изобр

(А (В (D (I), E (J, K, U), С (F (0), G (M, N), H (P)))} (b]

В

J К

С

cij*:. *-17. Представления древовидной структуры: (a) вложенные множе-** (b) вложенные скобки; (с) ломаная последовательность; (d) граф.

женного на рис. 4.17, равна 52. Очевидно, что средняя дд5 пути Pi есть

где П1 - число узлов на уровне L Для того чтобы опредедц.. что называется длиной внешнего пути, мы будем дополнят' дерево специальным узлом каждый раз, когда в нем встп - чается нулевое поддерево. При этом мы считаем, что все уз должны иметь одну и ту же степень - степень дерева. Следц! вательно, подобное расширение дерева предполагает запол!

Рис. 4.18. Два различных бинарных дерева,

нение пустых ветвей, разумеется, при этом специальные узлы не имеют дальнейших потомков. Дерево на рис. 4.17, допол. ненное специальными узлами, показано на рис. 4.19, где специальные узлы изображены квадратиками.

QDuduuuuuuuuuuQuduuQ QD Рис. 4.19. Тернарное дерево со специальными узлами.

Длина внешнего пути теперь определяется как сумма 0 путей всех специальных узлов. Если число специальных узл^ на уровне i есть m;, то средняя длина внешнего пути равна

1 .- (4.35)

Рр = -