· {L1, L2, ..., Lm} левое поддерево R

· {R1, R2, ..., Rm} правое поддерево R

На любом уровне n бинарное дерево может содержать от 1 до 2n узлов. Число узлов, приходящееся на уровень, является показателем плотности дерева. Интуитивно плотность есть мера величины дерева (число узлов) по отношению к глубине дерева. На Рис. 5 дерево А содержит 8 узлов при глубине 3, в то время как дерево B содержит 5 узлов при глубине 4. Последний случай является особой формой, называемой вырожденным (degenerate) деревом, у которого есть единственный лист (E) и каждый нелистовой узел имеет только одного сына. Вырожденное дерево эквивалентно связанному списку.

Рис.5. Бинарные деревья

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

Вырожденные деревья являются крайней мерой плотности. Другая крайность – законченные бинарные деревья (complete binary tree) глубины N, где каждый уровень 0...N - 1 имеет полный набор узлов, и все листья уровня N расположены слева. Законченное бинарное дерево, содержащее 2N узлов на уровне N, является полным. На Рис. 6 показаны законченное и полное бинарные деревья.

Рис.6. Классификация бинарных деревьев

Бинарные деревья классифицируются по нескольким признакам. Введем понятия степени узла и степени дерева. Степенью узла в дереве называется количество дуг, которое из него выходит. Степень дерева равна максимальной степени узла, входящего в дерево. Исходя из определения степени понятно, что степень узла бинарного дерева не превышает числа два. При этом листьями в дереве являются вершины, имеющие степень ноль.

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

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

Рис.8. Полное и неполное бинарные деревья

Рис.9. Строго и не строго бинарные деревья

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

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

Можно заметить, что такой способ представления имеет сходство с простыми линейными списками. И это сходство не случайно. На самом деле рассмотренный способ представления бинарного дерева является разновидностью мультисписка, образованного комбинацией множества линейных списков. Каждый линейный список объединяет узлы, входящие в путь от корня дерева к одному из листьев.

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

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

Рис.11. Представление бинарного дерева в виде массива

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

Однако далеко не все бинарные деревья являются полными. Для неполных бинарных деревьев применяют следующий способ представления. Бинарное дерево дополняется до полного дерева, вершины последовательно нумеруются. В массив заносятся только те вершины, которые были в исходном неполном дереве. При таком представлении элемент массива выделяется независимо от того, будет ли он содержать узел исходного дерева. Следовательно, необходимо отметить неиспользуемые элементы массива. Это можно сделать занесением специального значения в соответствующие элементы массива. В результате структура дерева переносится в одномерный массив. Адрес любой вершины в массиве вычисляется как

адрес = 2к-1+i-1,

где k-номер уровня вершины, i- номер на уровне k в полном бинарном дереве. Адрес корня будет равен единице. Для любой вершины можно вычислить адреса левого и правого потомков

адрес_L = 2к+2(i-1)