Лекция: Деревья

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

Специального вида граф, в котором в каждую вершину может входить только одна стрелка, а выходить несколько, называется деревом (рисю 14.2).

Уровни:

а б

Рис. 14.2. Изображение дерева (а); структура, не являющаяся деревом (б)

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

В дереве может быть только один путь от корня к узлу; дерево не содержит петель и циклов, что следует из определения.

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

П р и м е р ы деревьев

Факультет: 5 курсов, на каждом курсе – определенное число групп; в каждой группе – n человек.

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

Арифметическое выражение можно представить в виде деревьев, в узлах которых находятся операции, за исключением терминальных вершин. В них находятся переменные или числа (рис. 14.3).

Рис. 14.3. Формула в виде двоичного дерева

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