ПОСТРОЕНИЕ БИНАРНОГО ДЕРЕВА

Наибольший интерес представляет задача построения бинарного дерева минимальной высоты при заданном числе узлов п.

Очевидно, что минимальная высота достигается, если на всех уровнях, кроме последнего, помещается максимально возможное число узлов. Этого можно добиться, размещая очередные узлы поровну слева и справа от каждого узла. В результате будем получать деревья со структурой, приведенной на рис. 3.4:

Рис. 3.4. Построение бинарного дерева минимальной высоты

Правило равномерного распределения для известного числа узлов п лучше всего сформулировать, используя рекурсию:

• 1) взять один узел в качестве корня;
• 2) построить тем же способом левое поддерево с п1-п сНу 2 узлами;
• 3) построить тем же способом правое поддерево с пг = п-п1- узлами.

Построенное с помощью предложенного выше алгоритма дерево будет идеально сбалансированным — для каждого его узла число узлов в правых и левых поддеревьях отличается не более чем на 1.

ОПЕРАЦИИ НАД БИНАРНЫМ ДЕРЕВОМ

Над бинарным деревом могут быть выполнены следующие группы операций:

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

Обход (прохождение) дерева используется для систематического последовательного просмотра узлов дерева. Эта операция может быть использована для контроля информации, хранящейся в древовидной структуре, а также для выполнения других операций над деревом. Рекурсивная процедура обхода дерева включает в себя следующие шаги:

• 1) обработка (просмотр) корня дерева или поддерева;
• 2) обход левого поддерева обработанного корня;
• 3) обход правого поддерева обработанного корня;

Различный порядок выполнения перечисленных выше шагов

определяет три процедуры обхода бинарного дерева:

• 1) обход сверху вниз — сначала обрабатывается корень, затем обходится его левое, затем правое поддеревья (операция UpDown-Revision);
• 2) обход слева направо — сначала обходится левое поддерево корня, затем обрабатывается корень, затем обходится его правое поддерево (Left Right Revision);
• 3) обход снизу вверх — обходится левое поддерево корня, затем правое, затем обрабатывается корень (DownUpRevision).

При обходе каждого из приведенных на рис. 3.5 бинарных деревьев получим по три упорядоченные последовательности, приведенные в табл. 3.1.

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

Таблица 3.1

Результаты обхода деревьев на рис. 3.5

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

Поскольку бинарное дерево является упорядоченным, то должно быть указание на то, в качестве какой ветви (левой или правой) заданного узла должно быть подключено поддерево. Целесообразно разбить эту операцию на две: включение поддерева в качестве левой ветви заданного узла (AddLeft) и включение в качестве правой ветви заданного узла (AddRight).

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

Исключение некоторого поддерева из дерева фактически представляет собой две операции: исключение поддерева из левой ветви заданного узла исходного дерева (DeleteLeft) и исключение поддерева из его правой ветви (DeleteRight). Операция возвращает адрес исключенного поддерева.

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

• • Addr(v) возвращает адрес узла со значением v;
• • если р — указатель на узел бинарного дерева, то операция Value(p) возвращает значение этого узла;
• • операции Left(p), Right(p), Father(p), Brother(p) возвращают соответственно указатели на левого сына, правого сына, отца и брата узла с указателем р;
• • операции IsLeft(p) и IsRight(p) возвращают значение «истина», если узел с указателем р является соответственно левым или правым сыном некоторого узла дерева, и значение «ложь» — в противном случае.

Дополнительно могут быть определены операции:

• • Create — создание пустого дерева;
• • Clear — удаление всех узлов дерева;
• • WriteTo(f) — вывод дерева в файл f с помощью отступов;
• • NodesQuantity(p) — определение числа узлов поддерева с корнем р.