Понедельник, Июль 5th, 2010

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

Последовательность действий алгоритма приведена на рис. 4.6.

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

1. Обход дерева.
2. Удаление поддерева.
3. Вставка поддерева.

Для выполнения обхода дерева необходимо выполнить три процедуры:
1.Обработка корня.
2.Обработка левой ветви.
3.Обработка правой ветви.

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

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

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

4.2.3 Алгоритм создания дерева бинарного поиска
Пусть заданы элементы с ключами: 14, 18, 6, 21, 1, 13, 15. После выполнения нижеприведенного алгоритма получится дерево, изображенное на рис.4.6. Если обойти полученное дерево слева направо, то получим упорядочивание: 1, 6, 13, 14, 15, 18, 21.

Псевдокод

read (key, rec)
tree = maketree(key rec)
p = tree
q = tree
while not eof do
read (key, rec)
v = maketree(key, rec)
while p <> nil do
q = p
if key < k(p) then
p = left(p)
else
p = right(p)
endif
endwhile
if key < k(q) then
left(p) = v
else
right(p) = v
endif
if q=tree then
‘ только корень’
endif
return
Паскаль

read (key, rec);
tree := maketree(key rec);
p := tree;
q := tree;
while not eof do
begin
read (key, rec);
v := maketree(key, rec);
while p <> nil do
begin
q := p;
if key < p^.k then
p := p^.left
else
p := p^.right;
end;
if key < q^.k then
p^.left := v
else
p^.right := v;
end
if q=tree
then writeln(‘Только корень’);
exit

4.2.4 Прохождение бинарных деревьев
В зависимости от  последовательности обхода поддеревьев различают три вида обхода (прохождения) деревьев (рис.4.9):

1. Сверху вниз А, В, С.
2. Слева направо или симметричное прохождение В, А, С.
3. Снизу вверх В, С, А.

Страницы: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84

Категория: Учебники