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

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

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

Рис. 65. Примеры бинарных деревьев

Максимальное число узлов в бинарном дереве высотой h (d=2):

.

Максимальное число узлов на уровне i в бинарном дереве:

.

Высота полного бинарного дерева, содержащего Nузлов:

.

  означает взятие целой части числа.

Существуют различные алгоритмы преобразования дерева произвольной степени, т.е. дерева общего вида, к виду бинарного. Левосторонний алгоритм формулируется следующим образом: у каждого узла дерева произвольной степени необходимо сохранить самую левую связь, а узлы – потомки одного и того же узла следует соединить правой связью. На рис. 66 представлено исходное дерево общего вида, а на рис. – эквивалентное бинарное.

Рис. 66. Преобразование произвольного дерева к виду бинарного

7.3. Представление бинарных деревьев

7.3.1. Представление бинарных деревьев на статической

памяти

Если известен максимальный размер дерева (т.е. высота, а следовательно, и количество узлов, соответствующих полному дереву), то структуру дерева можно хранить в виде массива. При этом корень дерева будет храниться в элементе массива с индексом [1]. Для каждого узла с номеромkего левый потомок будет хранится в элементе с индексом[2 * k], а правый - в элементе с индексом[2 * k + 1] (см. рис. 67).

Рис. 67. Представление бинарного дерева на статической памяти

Достоинством представления бинарных деревьев на статической памяти является простота доступа как от предка к потомку, так и от потомка к предку, а недостатком - то, что если дерево не является полным, в массиве появляется большое число пустых элементов. Ограниченный размер массива не позволяет включать в дерево новые узлы, т.е. дерево не может “расти”. Удаление узла из дерева и соответствующее изменение его структуры потребует модификации содержимого массива.

7.3.2. Представление бинарных деревьев на

динамической памяти

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

Type
PTree = ^ Tree;	{ тип – указатель на узел дерева }
Tree = record	{ тип – элемент хранения узла дерева}
info: char;	{ информационное поле }
left, right: PTree	{ ссылки на поддеревья }
End;
Var Root: PTree;	{ указатель на корень дерева }

Дерево задается указателем на его корень. Если дерево пусто, указатель на его корень равен NIL. Связанное представление бинарного дерева иллюстрирует рис. 68.

Рис. 68. Связанное представление бинарного дерева