3. Операции над бинарным деревом

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

• обход узлов бинарного дерева в определенном порядке;

• добавление некоторого поддерева в дерево;

• исключение некоторого поддерева из дерева;

• примитивные операции над узлами дерева.

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

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

2) обход левого поддерева обработанного корня;

3) обход правого поддерева обработанного корня;

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

1) обход сверху вниз– сначала обрабатывается корень, затем обходится его левое, затем правое поддеревья (операцияUpDownRevision);

2) обход слева направо– сначала обходится левое поддерево корня, затем обрабатывается корень, затем обходится его правое поддерево (операцияLeftRightRevision);

3) обход снизу вверх– обходится левое поддерево корня, затем правое, затем обрабатывается корень (операцияDownUpRevision).

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

(а)(б)

обход дерево (а) дерево (б)

сверху вниз ABDEGCFHI+a/bc–def(префиксная запись)

слева направо DBGEACHFIa+b/cd–ef(инфиксная без скобок)

снизу вверх DGEBHIFCAabc/+def–(постфиксная запись)

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

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

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

Дополнительно могут быть определены следующие операции: Create– создание пустого дерева,Clear– удаление всех узлов дерева,WriteTo(f) – вывод дерева в файлfс помощью отступов,NodesQuantity– определение числа узлов дерева.