ОПРЕДЕЛЕНИЕ. Корневое дерево называется бинарным, если каждая его вершина связана не более чем с двумя вершинами следующего яруса.
Корневое дерево называется бинарным, если каждая его вершина связана не более чем с двумя вершинами следующего яруса.
Для бинарных деревьев может быть использована специальная форма представления.
Пусть D - бинарное дерево с n вершинами.
1. Перенумеруем вершины числами от 1 до n.
2. Представим D в виде корневого дерева.
3. Потомков каждой вершины (если они имеются) назовем левым и правым потомками, если такой потомок один, то это всегда левый потомок.
4. Заполним два массива L = (l 1,..., ln) и R = (r 1,..., rn) по следующему правилу: li равно номеру левого потомка вершины дерева D, которая получила номер i. Если вершина с номером i не имеет такого потомка, то li = 0. Значение ri определяется аналогично, но для правого потомка вершины с номером 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
Для графов, являющихся деревьями, справедлив следующий простой критерий.
Дата добавления: 2015-09-27 | Просмотры: 406 | Нарушение авторских прав
|