предка. Далее для обозначения родства, которое может простираться на несколько уровней дерева, будут использоваться термины "предок" (ancestor) и "потомок" (descendant). Например, потомками узла С на рис. 19 являются узлы D, Е, F п G, а. предками узла G - узлы Е,С п А.

Родословная, показанная на рис. 18, (а), является примером бинарного дерева (binary tree)-одного из паи- Рис. 19. Обычная , схема дерева

более важных типов деревьев. Читатель наверняка не

раз встречался с бинарными деревьями в соревнованиях по теннису или других турнирах, которые проводятся по олимпийской системе с выбыванием проигравшего. Каждый узел бинарного дерева имеет не более двух поддеревьев, причем в случае только одного поддерева следует различать левое и правое. Строго говоря, бинарное дерево - это конечное множество узлов, которое является пустым плп состоит пз корня и двух непересекающихся бинарных деревьев, которые называются левым и правым поддеревьями данного корня.

Тщательно изучим это рекурсивное определение бинарного дерева. Обратите внимание на то, что бинарное дерево не является особым типом ранее определенного обычного дерева. На самом деле это совершенно другое понятие (хотя впоследствии мы увидим, что у них есть много общего). Например, бинарные деревья

являются различными, так как в первом случае корень имеет пустое правое поддерево, а в другом - пустое левое поддерево. Однако как деревья они совершенно идентичны. Бинарное дерево может быть пустым, а обычное дерево - нет. Следовательно, при работе с бинарными деревьями нужно не забывать об обязательном эпитете "бинарный", чтобы не путать их с обычными деревьями. Некоторые авторы предлагают несколько иное определение бинарного дерева (см. упр. 20).

Древовидную структуру можно представить графически несколькими способами, которые могут выглядеть совершенно не так, как настоящие деревья в природе. На рис. 20 показаны три способа представления структуры с рис. 19: по сути, на рис. 20, (а) дерево с рис. 19 представлено в виде ориентированного дерева {oriented tree). Эта схема является частным случаем вложенных множеств {nested sets), а именно - набором множеств, в котором либо каждая пара множеств не пересекается, либо одно множество содержит другое (см. упр. 10). Если на рис. 20, (а) вложенные множества расположены в одной плоскости, то на рис. 20. (Ь) они находятся на одной линии, причем таким образом указывается и упорядочение данного дерева. Схема на рис. 20, (Ь) может рассматриваться как некая алгебраическая формула с вложенными скобками. Наконец, на рис. 20, (с) показан еще один общий способ представления древовидных структур с использованием отступа {indentation) . Само по себе количество разных методов представления является прекрасным доказательством важности древовидных структур как в повседневной жизни, так и в программировании. В итоге любая классификация с иерархической структурой имеет древовидную структуру.

{A{B{H){J)){C{D){E{G)){F))) (b)

Рис. 20. Способы изображения древовидных структур: (а) вложенные множества; (Ь) вложенные скобки; (с) список с отступами.

Алгебраическая формула неявным образом определяет древовидную структуру, которая часто обозначается другими средствами, причем либо вместе со скобками, либо совсем без них. Например, на рис. 21 показано дерево, соответствующее арифметическому выражению

a-b{c/d+e/f). (2)

Согласно стандартным математическим соглашениям операции умножения и деления обладают приоритетом по сравнению с операциями сложения и вычитания. Благодаря этому приведенное выше выражение можно представить в упрощенном виде (2), а не в виде а - (ft х ((c/d) + (е ))), в котором все части выражения заключены в скобки. Эта связь между формулами и деревьями особенно важна при создании приложений.

с) [d) {е] (f Рис. 21. Представление формулы (2) в виде дерева.

Обратите внимание на то, что список с отступами, показанный на рис. 20, (с), очень похож на оглавление данной книги. Действительно, даже сама эта книга обладает древовидной структурой. Например, древовидная структура главы 2 показана на рис. 22. Здесь следует отметить одну важную особенность: нумерация разделов в настоящеП книге представляет собой еще один способ представления древовидной структуры. Этот метод часто назьшается десятичной системой обозначений Дьюи (Dewey decimal notation) по аналогии с подобной классификационной схемой, применяемой в библиотеках. Для дерева, представленного на рис. 19, она будет

выглядеть так:

1А; 1.1В; 1.1.1 Н; 1.1.2 J; 1.2 С; 1.2.1JD; 1.2.2 Е; 1.2.2.1 G; 1.2.3 F.

Десятичную систему обозначений Дьюи можно применять по отношению к любому лесу: корень к-го дерева леса задается числом к, и, если а - количество узлов степени т, его дети будут обозначаться как а.1,а.2,... ,а.т. Десятичная система обозначений Дьюи обладает многими простыми математическими свойствами и является полезным инструментом для анализа деревьев. Одним из примеров является естественное последовательное упорядочение узлов произвольного дерева, которое аналогично упорядочению разделов данной книги. "Например, раздел 2.3 предшествует разделу 2.3.1 и располагается за разделом 2.2.6.

Между системой десятичных обозначений Дьюи и индексной системой обозначения переменных, которая неоднократно использовалась выше, существует довольно близкая связь. Если F - это лес деревьев, то F[l] - все множество поддеревьев первого дерева, F[l][2] = F[l,2] - множество поддеревьев второго поддерева из множества F[l], а F[l,2,1] - первое множество поддеревьев первого поддерева из множества F[l,2] и т. д. Обозначение узла a.b.c.d в десятичной системе обозначений Дьюи соответствует узлу-родителю множества поддеревьев {F[a,b,c,d\). Это обозначение является расширением обычного индексного обозначения, поскольку допустимый диапазон значений каждого индекса зависит от значений индексов на предыдущих уровнях. Так, любой прямоугольный массив можно рассматривать как особый случай древовидной структуры, что и проиллюстрировано ниже на примере матрицы размера 3x4.

/А{1,1] А[1,2] А[1,3] А[1,4]\

А[2,1] А[2,2] А[2,3] А[2,4] \А[3,1] А[3,2] А[3,3] A[3,4]J

cs fO

cs fO

££ £f c£

1-1 (П fo" ,fO fo" ,fO

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

В свою очередь, лес можно рассматривать как особую структуру списка (list structure). Слово "список" здесь применяется в очень специфическом смысле, и, чтобы подчеркнуть это, его пишут с прописной буквы: "Список". Рекурсивно Список определяется как конечная последовательность атомов или Списков, число которых может быть больше или равно нулю. Здесь под словом "атом" подразумевается неопределенное понятие, которое может относиться к элементам любой совокупности объектов и которое можно отличить от Списка. С помощью обычной системы обозначений на основе запятых и скобок можно различать атомы и Списки, а также быстро и просто указывать упорядочение в пределах Списка.