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

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

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

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

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

.

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

.

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

.

ë û означает взятие целой части числа.

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

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