2.4. ДЕРЕВЬЯ

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

Определение. Ориентированный граф без циклов называется ориентированным ациклическим графом. (Ориентированное) дерево (иногда его называют корневым деревом) — это ориентированный ациклический граф, удовлетворяющий следующим условиям:

1) имеется в точности один узел, называемый корнем, в который не входит ни одно ребро,

2) в каждый узел, кроме корня, входит ровно одно ребро,

3) из корня к каждому узлу идет путь (который, как легко показать, единствен).

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

Определение. Пусть граф, являющийся лесом. Если принадлежит то называется отцом узла сыном узла Если есть путь из то называется предком узла потомком узла Более того, если ъфхю, то называется подлинным предком узла подлинным потомком узла у. Узел без подлинных потомков называется листом. Узел и его потомки вместе образуют поддерево леса и узел называется корнем этого поддерева.

Рис. 2.7. Двоичное дерево и его представление.

Глубина узла в дереве — это длина пути из корня в Высота узла в дереве — это длина самого длинного пути из и в какой-нибудь лист. Высотой дерева называется высота его корня. Уровень узла в дереве равен разности высоты дерева и глубины узла Например, на рис. 2.7, а узел 3 имеет глубину 2, высоту и уровень 1.

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

1) каждый сын произвольного узла идентифицируется либо как левый сын, либо как правый сын,

2) каждый узел имеет не более одного левого сына и не более одного правого сына.

Поддерево корнем которого является левый сын узла (если такое существует), называется левым поддеревом узла Аналогично поддерево корнем которого является правый сын узла (если такое существует), называется правым поддеревом узла Все узлы в расположены левее всех узлов в

Двоичное дерево обычно представляют в виде двух массивов и Пусть узлы двоичного дерева занумерованы целыми числами от 1 до . В этом случае тогда и только тогда, когда узел с номером является левым сыном узла с номером Если у узла нет левого сына, то определяется аналогично.

Пример 2.3. Двоичное дерево и его представление изображены на рис. 2.7.

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

Полное двоичное дерево высоты часто представляют одним массивом. В позиции 1 этого массива находится корень. Левый сын узла в позиции I расположен в позиции а его правый сын — в позиции Отец узла, находящегося в позиции расположен в позиции

Многие алгоритмы, использующие деревья, часто проходят дерево (посещают каждый его узел) в некотором порядке. Известно несколько систематических способов сделать это. Мы рассмотрим три широко распространенных способа: прохождение дерева в прямом порядке, обратном и внутреннем.

Рис. 2,8, Прохождение дерева: а — в прямом порядке; б - обратном; в — внутреннем.

Определение. Пусть дерево с корнем и сыновьями При это дерево состоит из единственного узла

Прохождение дерева в прямом порядке определяется следующей рекурсией:

1) посетить корень

2) посетить в прямом порядке поддеревья с корнями в указанной последовательности.

Прохождение дерева в обратном порядке определяется следующей рекурсией:

1) посетить в обратном порядке поддеревья с корнями в указанной последовательности,

2) посетить корень

Прохождение двоичного дерева во внутреннем порядке определяется следующей рекурсией:

1) посетить во внутреннем порядке левое поддерево корня (если оно существует),

2) посетить корень,

3) посетить во внутреннем порядке правое поддерево корня (если оно существует).

Пример 2.4. На рис. 2.8 изображено двоичное дерево, узлы которого пронумерованы в соответствии с прохождением его в прямом порядке (рис. 2.8,а), обратном и внутреннем (рис. 2.8,в).

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

Если все узлы занумерованы в порядке посещения, то рассмотренные нумерации обладают рядом интересных свойств.

При нумерации в прямом порядке все узлы поддерева с корнем имеют номера, не меньшие Точнее, если множество потомков узла то будет номером некоторого узла из тогда и только тогда, когда Поставив в соответствие каждому узлу его номер в прямом порядке и количество его потомков, легко определить, является ли некоторый узел потомком для После того как номера присвоены (в соответствии с прямым порядком) и вычислено количество потомков каждого узла, на вопрос, является ли потомком для можно ответить за фиксированное время, не зависящее от размера дерева. Номера, соответствующие обратному порядку, обладают аналогичным свойством.

Номера узлов двоичного дерева, соответствующие внутреннему порядку, обладают тем свойством, что номера узлов в левом поддереве для меньше а в правом поддереве больше Таким образом, чтобы найти узел с номером надо сравнить с корнем Если то искомый узел найден. Если то надо повторить этот процесс для левого поддерева; если то повторить процесс для правого поддерева. В конце концов узел с номером будет найден. Такие свойства прохождений нам понадобятся в следующих главах.

Дадим теперь еще одно, последнее определение, касающееся деревьев.

Определение. Неориентированным деревом называется неориентированный ациклический связный (любые два узла соединены путем) граф. Корневое неориентированное дерево — это неориентированное дерево, в котором один узел выделен в качестве корня.

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