Теоретические сведения. Бинарное (двоичное) дерево – это динамическая структура данных, состоящая из элементов, каждый из которых содержит информационное поле и не более двух ссылок

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

· информационное поле (ключ вершины);

· служебное поле (их может быть несколько или ни одного);

· указатель на левое поддерево;

· указатель на правое поддерево.

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

На рисунке схематично представлена структура бинарного дерева, у которого все узлы до 3 уровня имеют по два потомка, а все узлы уровня 3 являются листами.

Рис. Бинарное дерево

Список можно представить как частный случай бинарного дерева:

Рис. Список как частный случай бинарного дерева

Структура дерева отражается во входном потоке данных так: каждой вводимой пустой связи соответствует условный символ, например, '*' (звездочка). При этом сначала описываются левые потомки, затем, правые. Для структуры бинарного дерева, представленного на следующем рисунке, входной поток имеет вид: ABD*G***CE**FH**J**.

Рис. Адресация в бинарном дереве

Описание бинарного дерева выглядит следующим образом:

struct имя_типа {

информационное поле;

[служебное поле;]

адрес левого поддерева;

адрес правого поддерева;

};

где информационное поле – это поле любого ранее объявленного или стандартного типа;

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

Например:

struct point {

int data;//информационное поле

int count; //служебное поле

point *left;//адрес левого поддерева

point *right;//адрес правого поддерева

};

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

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

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

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

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