7 Древовидные структуры данных

7.1 Основные понятия и определения

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

Автомобиль

I

Агрегаты

! Узлы

i Детали

Деревом называется структура, которая характеризуется следующими свойствами:

1. существует единственный элемент, на который не ссылается никакой другой элемент. Этот элемент на­зывается корнем.

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

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

или листьями. А элементы, не являющиеся терминальными, называются внутренними узлами.

Таким образом дерево отражает иерархически упорядоченную структуру данных, в которой прослежива­ются связи между элементами предыдущего (верхнего) уровня или предками и элементами следующего уровня - потомками.

Можно считать список деревом, у которого каждый узел имеет не более одного "поддерева". Поэтому список называется также "вырожденным деревом".

Существует несколько способов изображения древовидной структуры. Например, пусть базовый тип Т есть множество букв. Древовидную структуру, образованную с какой-либо целью на таком типе можно изобра-

зить, например:

а) вложенными множествами (рис. 17);

Рис. 17

б)вложенными скобками

(A(B(D(I), E(J, K, L)), C(F(O), G(M, N), H(P) )));

в)графом (рис. 18).

Рис. 18

Графом дерево представляется нагляднее, но вверх ногами (корнем).

Узлы располагаются по уровням. Корень – нулевой уровень и т.д. Максимальный уровень какого-либо элемента дерева называется его глубиной или высотой.

Число непосредственных потомков внутреннего узла называется его степенью. Максимальная степень всех узлов есть степень дерева. Наше дерево – дерево третьей степени.

Число ветвей или ребер, которые нужно пройти, чтобы продвинуться от корня к узлу х, называется длиной пути к х. Корень имеет длину пути 0, его непосредственные потомки – длину пути 1 и т.д. Вообще узел на уровне i имеет длину пути i.

Длина пути дерева – это сумма длин путей всех его узлов. Она также называется длиной внутреннего пу­ти. Для нашего дерева длина пути равна 36. Средняя длина пути

1

P_c

ср

П

Hni-

i = \

где n_i – число узлов на уровне i; n – число элементов.

Дерево, у которого ветви каждого узла упорядочены, называется упорядоченным деревом:

разные упорядоченные деревья

Особо важную роль играют упорядоченные деревья второй степени. Они называются бинарными деревь­ями или двоичными. Бинарное дерево – это конечное множество элементов (узлов), каждый из которых либо пуст (не связан с нижним уровнем, не имеет потомков, т.е. лист), либо является корнем (или узлом) с двумя различными бинарными поддеревьями – левым и правым.

Деревья, имеющие степень больше двух, называются сильно ветвящимися деревьями.

Пример бинарного дерева – Арифметическое выражение с двуместными операциями, где каждая операция – это ветвящийся узел с операндами в качестве поддеревьев, например выражение (a + b / c) * (d - e * f), пред­ставится в виде двоичного дерева следующим образом

В принципе, любое n–арное дерево может быть преобразовано в эквивалентное ему бинарное дерево.