книги / Технологии разработки объектно-ориентированных программ на язык C++. Представление графических объектов и проектирование программ на алгоритмическом языке C++

3

ГЛАВА 22. БИНАРНЫЕ ДЕРЕВЬЯ

22.1. Понятие дерева

Определения

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

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

Дерево – граф иерархической структуры. Между любыми двумя его вершинами существует единственный путь. Дерево не содержит циклов и петель, является связным графом, не содержащим циклы (см. гл. 23).

Сравнение дерева со списком

Массивы и связанные списки определяют коллекции объектов, доступ к которым осуществляется последовательно, т.е. эти объекты находятся в определенном порядке. Такие структуры данных называются линейными списками, поскольку имеют уникальные первый и последний элементы и у каждого внутреннего элемента есть только один потомок (рис. 22.1).

Рис. 22.1. Список и дерево (визуальное сравнение)

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

5

название происходит от церковного распределения власти – от епископа к пасторам, дьяконам и т.д. Одной из нелинейных структур является дерево. При этом список – это частный случай дерева, т.е. это дерево, где у каждого узла, кроме нижнего, есть только один потомок.

Некоторые термины

Прежде чем анализировать деревья, следует познакомиться с некоторыми терминами, связанными с ними. Рассмотрим дерево, показанное на рис. 22.2.

Рис. 22.2. Пример дерева

Все одиночные элементы – узлы дерева:

•A – самый верхний узел дерева, корень;

•B, C, D, E, F – внутренние узлы дерева;

•G, H, I – самые нижние узлы дерева, терминальные узлы,

или листья.

Более сложные структуры:

•A–B, A–C, B–D, B–E, C–F, E–G, F–H, F–I – ветви дерева;

•дерево с верхним узлом B – поддерево дерева с верхним уз-

лом А.

Характеристики узлов:

•C – узел, являющийся потомком узла A и предком узла F;

•узел A находится на уровне 1, так как это корень дерева, узлы B и C – на уровне 2. Таким образом, если элемент X находится на уровне i, то его потомок Y находится на уровне i + 1;

•число непосредственных потомков внутреннего узла – его степень. Например, степень узла В равна 2;

6

•число ветвей, которые нужно пройти от корня до узла, – длина пути. Так, длина пути к узлу I равна 3.

Характеристики дерева:

•максимальный уровень элементов дерева называется высотой дерева (в данном случае высота дерева равна 4);

•максимальная степень всех узлов дерева называется степенью дерева (в данном случае степень дерева равна 2);

•сумма длин путей всех его узлов называется длиной внутреннего пути дерева (в данном случаедлина внутреннего путиравна17).

Свойства и особенности дерева

Каждое дерево обладает следующими свойствами:

•существуетузел, в который не входитни одной ветви (корень);

•в каждую вершину, кроме корня, входит одна ветвь.

Рис. 22.3. Генеалогическое дерево

7

Деревья являются рекурсивными структурами, так как каждое поддерево также является деревом. Таким образом, дерево можно определить как рекурсивную структуру, в которой каждый элемент является:

•либо пустой структурой;

•либо элементом, с которым связано конечное число подде-

ревьев.

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

Примеры использования деревьев

Деревья особенно часто используют на практике при изображении различных иерархий. Например, популярны генеалогические деревья (рис. 22.3).

Кроме того, деревья описывают управляющий аппарат компании, во главе которой стоит президент, а далее идут начальники отделов и менеджеры (рис. 22.4).

Рис. 22.4. Дерево управления компанией

22.2. Бинарные деревья

Упорядоченные и бинарные деревья

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

8

имеет не более двух потомков. Но прежде стоит уделить внимание следующему понятию.

Упорядоченное дерево – это дерево, у которого ветви каждого узла упорядочены.

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

На рис. 22.5 представлены два различных упорядоченных дерева. Два потомка одного узла вместе с их поддеревьями поменялись местами, и получилось совершенно другое дерево. Если не считать дерево упорядоченным и поменять местами некоторых потомков, то ничего не изменится, дерево будет тем же.

Рис. 22.5. Примеры упорядочивания деревьев

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

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

Классификация бинарных деревьев

Бинарные деревья имеют унифицированную структуру, допускающую разнообразные алгоритмы прохождения и эффективный доступ к элементам.

По степени узлов бинарные деревья делятся:

•на строгие: узлы дерева имеют степень либо 0 (листья), либо 2 (внутренние узлы) (рис. 22.6);

•нестрогие: узлы дерева имеют степень либо 0 (листья), либо 1–2 (внутренние узлы) (см. рис. 22.6),

9