Определение

Корневое дерево называется бинарным, если каждая его вершина связана не более чем с двумя вершинами следующего яруса.

Для бинарных деревьев может быть использована специальная форма представления.

Пусть D  бинарное дерево с n вершинами.

1. Перенумеруем вершины числами от 1 до n.

2. Представим D в виде корневого дерева.

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

4. Заполним два массива L = (l₁, ... , l_n) и R = (r₁, ... , r_n) по следующему правилу: l_i равно номеру левого потомка вершины дерева D, которая получила номер i. Если вершина с номером i не имеет такого потомка, то l_i = 0. Значение r_i определяется аналогично, но для правого потомка вершины с номером i.

Например, корневое дерево на рис. 5.16 представляется массивами

L = (2, 8, 7, 0, 0, 0, 0, 4, 0) и

R = (3, 5, 9, 0, 0, 0, 0, 6, 0).

1

2 3

8 5 7 9

4 6

Рис. 5.16

Для графов, являющихся деревьями, справедлив следующий простой критерий.

Теорема 5.4

Неориентированный связный граф без петель G = (V, U) является деревом тогда и только тогда, когда |V| = |U| + 1.

Доказательство

Необходимость. ( ) Пусть G = (V, U)  дерево. Покажем, что |V| = |U| + 1. Рассмотрим некоторое корневое представление G.

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

Очевидно, что через конечное число выполнений приведенного преобразования от графа G останется только корневая вершина.

Поскольку число удаленных при этом вершин равно числу удаленных ребер и одна вершина графа G осталась, то |V| = |U|+1.

Достаточность. ( ) Пусть G = (V, U)  неориентированный связный граф без петель, для которого |V| = |U| + 1. Покажем, что G  это дерево.

Предположим противное: G не является деревом. Следовательно, в G имеются циклические ребра.

Выполним процедуру последовательного размыкания циклов в G, не нарушающего связности этого графа. Она основана на следующем элементарном действии: выбирается произвольный элементпрный цикл в G, длина которого не меньше чем 3, после чего из G удаляется любое ребро этого цикла.

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

Заданное преобразование графа заканчивается за конечное время и полученный в результате граф является связным.

Обозначим этот граф как G^* = (V, U^*). Поскольку G^* не содержит циклических ребер, то он является деревом.

Поэтому из доказательства необходимости следует справедливость равенства: |V| = |U^*| + 1.

Последнее противоречит начальному предположению о том, что |V| = |U| + 1, поскольку по построению графа G^* должно выполняться неравенство: |U^*| < |U|.

Полученное противоречие означает, что G не может содержать циклических ребер и является деревом.

Доказательство окончено.