Реализация полученного бинарного дерева с помощью нелинейного двусвязного списка

Основные операции с деревьями

1. Обход дерева.

2. Удаление поддерева.

3. Вставка поддерева.

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

1.Обработка корня.

2.Обработка левой ветви.

3.Обработка правой ветви.

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

1.Обход сверху вниз. Процедуры выполняются в последовательности 1-2-3.

2.Обход слева направо. Процедуры выполняются в последовательности 2-1-3.

3.Обход снизу вверх. Процедуры выполняются в последовательности 2-3-1.

A-B-C-E-D-F-G – сверху вниз

C-B-D-E-F-A-G – слева направо

C-D-F-E-B-G-A – снизу вверх

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

Операция исключения поддерева. Необходимо указать узел, к которому подсоединяется исключаемое поддерево и индекс этого поддерева. Исключение поддерева состоит в том, что разрывается связь с исключаемым поддеревом, т. е. указатель элемента устанавливается в nil, а степень исхода данного узла уменьшается на единицу.

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