Тема 15.1. Деревья

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

· имеется в точности один узел, называемый корнем, в который не входит ни одно ребро;

· в каждый узел, кроме корня, входит ровно одно ребро;

· из корня к каждому узлу идёт путь (который, как легко показать единственный).

Деревья являются простейшим видом связных графов. Любое дерево с вершинами содержит ребро. Число различных деревьев, которые можно построить на вершинах равно .

Определение: Дерево с одной выделенной вершиной называется корневым деревом.

Определение: Ориентированный граф, состоящий из нескольких деревьев, называется лесом.

Определение: Пусть – дерево. Если дуга , то называется отцом узла , а – сыном узла .

Определение: Если есть путь из в , то называется предком узла , а – потомком узла .

Определение: Узел без потомков называется листом.

Определение: Узел и его потомки вместе образуют поддерево леса , и узел называется корнем этого поддерева.

Определение: Глубина узла в дереве – это длина пути из корня в .

Определение: Высота узла в дереве – это длина самого длинного пути из этого узла в какой-нибудь лист.

Определение: Высотой дерева называется высота его корня.

Пример 15.1:

Глубина узла , в данном примере, = 1, а его высота = 2. Высота дерева = 3.

Определение: Упорядоченным деревом называется дерево, в котором множество сыновей каждого узла упорядоченно. При изображении упорядоченного дерева, как правило, считается, что множество сыновей каждого узла упорядоченно слева направо.

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

· каждый сын произвольного узла идентифицируется либо как левый сын, либо как правый сын;

· каждый узел имеет не более одного левого и не более одного правого сына.

Обратите внимание, что бинарное дерево не является частным случаем дерева, это совершенно иное, хотя и тесно связанное понятие.

Пример 15.2:

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

Определение: Бинарное дерево называется полным, если для некоторого целого числа каждый узел, глубины меньшей имеет как левого, так и правого сына, и каждый узел глубины является листом.

Полное дерево глубины имеет узлов.

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

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

Прохождение дерева в прямом порядке:

· посетить корень ;

· посетить слева на право поддеревья с корнями .

Пример 15.3:

Прохождение дерева в обратном порядке:

· посетить слева направо поддеревья с корнями ;

· посетить корень .

Пример 15.4:

Прохождение дерева во внутреннем порядке:

· посетить левое поддерево корня (если оно существует);

· посетить корень;

· посетить правое поддерево корня (если оно существует).

Пример 15.5:

Прежде чем дать описание одного из этих алгоритмов на некотором более формальном языке, поговорим о способах задания и хранения и бинарных деревьев. Бинарные деревья, как правило, хранятся посредством двух массивов ЛЕВЫЙСЫН и ПРАВЫЙСЫН, где номер элемента массива – это номер узла, а значение этого элемента – номер левого или правого узла – сына. Если элемент - сын отсутствует, то значение равно 0.

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

Вход: Двоичное дерево, представленное массивами ЛЕВЫЙСЫН и ПРАВЫЙСЫН.

Выход: Массив, называемый НОМЕР, такой, что НОМЕР[i] – номер i - того узла во внутреннем порядке.

Метод: Будем использовать глобальную переменную СЧЕТ, значение которой – номер очередного узла в соответствии с внутренним порядком. Начальное значение переменной СЧЕТ = 1.

Программа выглядит так:

begin

СЧЕТ 1

ВНУТРПОРЯДОК(КОРЕНЬ)

End

Procedure ВНУТРПОРЯДОК(УЗЕЛ)

Begin

if ЛЕВЫЙСЫН[УЗЕЛ]¹0 then

ВНУТРПОРЯДОК(ЛЕВЫЙСЫН[УЗЕЛ]);

НОМЕР[УЗЕЛ] СЧЕТ;

СЧЕТ СЧЕТ+1

if ПРАВЫЙСЫН[УЗЕЛ]¹0 then

ВНУТРПОРЯДОК(ПРАВЫЙСЫН[УЗЕЛ]);

End

Такая процедура, которая явно или неявно вызывает сама себя, называется рекурсивной. Применение рекурсии часто даёт возможность давать более прозрачное и сжатое описание алгоритма, чем это же можно было бы сделать, не используя рекурсию. Если бы приведённый алгоритм не был записан рекурсивно, надо было бы строить явный механизм для прохождения дерева. Двигаться вниз по дереву нетрудно, но чтобы обеспечить возможность вернуться к предку, надо запомнить всех предков в стеке, а операторы работы со стеком усложнили бы алгоритм, лишив его наглядности.

Дата добавления: 2015-10-28