Основные операции с деревьями
1. Обход дерева.
2. Удаление поддерева.
3. Вставка поддерева.
Для выполнения обхода дерева необходимо выполнить три процедуры:
1.Обработка корня.
2.Обработка левой ветви.
3.Обработка правой ветви.
В зависимости от того, в какой последовательности выполняются эти три процедуры, различают три вида обхода.
1.Обход сверху вниз. Процедуры выполняются в последовательности
1- 2 - 3.
2.Обход слева направо. Процедуры выполняются в последовательности
2 - 1- 3.
3.Обход снизу вверх. Процедуры выполняются в последовательности
2 - 3 -1.
В зависимости от того, какой по счету заход в узел приводит к обработке узла, получается реализация одного из трех видов обхода. Если обработка идет после первого захода в узел, то сверху вниз, если после второго, то слева направо, если после третьего, то снизу вверх (см. рис. 4. 7).
Операция исключения поддерева. Необходимо указать узел, к которому подсоединяется исключаемое поддерево и индекс этого поддерева. Исключение поддерева состоит в том, что разрывается связь с исключаемым поддеревом, т. е. указатель элемента устанавливается в nil, а степень исхода данного узла уменьшается на единицу.
Вставка поддерева - операция, обратная исключению. Надо знать индекс включаемого поддерева, узел, к которому подвешивается дерево, установить указатель этого узла на корень поддерева, а степень исхода данного узла увеличивается на единицу. При этом в общем случае необходимо произвести перенумерацию сыновей узла, к которому подвешивается поддерево.
Алгоритм вставки и удаления рассмотрен в главе 5.
