Структуры и алгоритмы обработки данных

       

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


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

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

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

 

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

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

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

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

 

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

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

1- 2 - 3.

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

2 - 1- 3.

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

2 - 3 -1.

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

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

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

Алгоритм  вставки и удаления  рассмотрен  в  главе 5.



Содержание раздела