Ориентированные и упорядоченные деревья

Пусть G –дерево с n > 1 вершинами. Зафиксируем одну из вершин v0 и назовем ее корнем. Выделение корня определяет на множестве вершин некоторое естественное отношение частичного порядка (ориентацию): вершина u предшествует вершине v (а вершина v следует за вершиной u), если u

встречается на пути из корневой вершины v0 в вершину v. Если к тому же вершины u и v связаны дугой, то u называется непосредственно предшествующей вершине v (а v – непосредственно следующей за u). Говорят, что вершина v, удаленная на расстояние k от корневой вершины, расположена на уровне k (или является вершиной уровня k). Значение уровня согласуется с отношением порядка: если вершина u предшествует вершине v, то уровень u меньше уровня v. Обратное, вообще говоря, неверно. Представляя дерево графически, вершины обычно располагают так, чтобы значение уровня увеличивалось в направлении сверху вниз.

На рис. 5 представлено дерево, в котором вершина 0 является корнем; вершины 1 и 2 находятся на первом уровне, вершина 3 – на третьем; вершина 1 предшествует вершине 3; вершины 1 и 3 с вершиной 2 отношением предшествования не

связаны.

0

Рис. 5

Вершины, за которыми не следует ни одна вершина, называют концевыми, или, в «древесном» стиле, – листьями. На рис. 5 вершина 3 является листом, всего же дерево на этом

рисунке имеет 7 листьев. У деревьев с выделенным корнем вершины часто называют узлами. Неконцевые узлы называют узлами ветвления. Число вершин, непосредственно следующих за узлом ветвления, называют степенью ветвления этого узла. На рис 5 узлы 0 и 1 имеют степень ветвления 2, узел 2 – степень 3.

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

(см. рис 5), получим пару деревьев, изображенных на рис. 6.

1

2

Рис. 6

С учетом этого можно дать следующее рекурсивное определение дерева с корнем (или ориентированного дерева). Дерево с корнем T – это конечное множество, состоящее из одного или более узлов таких, что:

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

2) остальные узлы разбиты на m ≥ 0 попарно непересекающихся множеств, каждое из которых в свою очередь является деревом.

Например, дерево на рис. 7 можно описать следующим

образом:

T = {1, T2}, T2 = {2, T3, T4}, T3 = {3, T5, T6, T7},

T5 = {5}, T6 = {6}, T7 = {7},

T4 = {4, T8}, T8 = {8, T9, T10}, T9 = {9}, T10 = {10}.

В явном виде это описание выглядит так:

T = {1; {2; {3; {5}, {6}, {7}}, {4; {8; {9}, {10}}}}}.

1

3 2 4

5 6 7

9 10

Рис. 7

Если в рекурсивном определении ориентированного дерева считать существенным порядок, в котором перечисляются поддеревья, растущие из заданного корня, получается определение упорядоченного дерева. Например, дерево с рис. 7 можно представить как упорядоченное дерево

T = (1; (2; (3; (5, 6, 7)), (4; (8; (9, 10))))).

Возможно и иное представление. Например,

T’ = (1; (2; (4; (8; (9, 10))), (3; (5, 6, 7)))).

Более формально:

1) всякий узел a является упорядоченным деревом с корнем a;

2) если a – некоторый узел, а T1, T1, …, Tm, m≥0, – упорядоченные деревья, то T = (a; (T1, T1, …, Tm)) – упорядочен- ное дерево с корнем a.

Упорядоченные деревья – одна из наиболее распространен-

ных информационных и алгоритмических структур.

Например, дерево на рис. 8 задает алгоритм вычисления значения арифметического выражения (1+2) – (3/4)2.

+ –

^2

/

1 2

3 4

Рис. 8