ОПРЕДЕЛЕНИЕ. Корневое дерево называется бинарным, если каждая его вершина связана не более чем с двумя вершинами следующего яруса

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

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

Пусть 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

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