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

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

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

 

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

.

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

.

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

.

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

 

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