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

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

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

READ(key,rec)
tree=maketree(key,rec)
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)
END IF
END WHILE
IF P=nil
THEN WRITELN(‘ Это корень’);
tree=V
ELSE IF key<k(q)
THEN left(P)=V
ELSE right(P)=V
END IF
END IF
END WHILE
Процедуры «обхода» дерева
Пусть задано бинарное дерево :

Существуют три принципа обхода бинарных деревьев. Рассмотрим их на примере заданного дерева :
1) Обход сверху вниз (корень посещается ранее, чем поддеревья) : A, B, C ;
2) Слева направо : B, A, C ;
3) Снизу вверх (корень посещается после поддеревьев) : B, C, A .
Наиболее часто применяется 2-ой способ, узлы посещаются в порядке возрастания значения их ключа.

Рекурсивные процедуры обхода дерева :
1) PROCEDURE pretrave (tree)
IF tree<>nil
THEN PRINT info (tree)
pretrave (left (tree))
pretrave (right (tree))
END IF
RETURN
2) PROCEDURE intrave (tree)

IF tree<>nil
THEN intrave (left (tree))
PRINT info (tree)
intrave (right (tree))
END IF
RETURN
3) PROCEDURE postrave (tree)

IF tree<>nil
THEN postrave (left (tree))
postrave (right (tree))
PRINT info (tree)
END IF
RETURN
Процедура поиска по бинарному дереву
Назначение этой процедуры в том, чтобы по заданному ключу осуществить поиск узла дерева. Длительность операции поиска (число узлов, которое надо перебрать для этой цели) зависит от структуры дерева. Действительно, дерево может быть вырождено в однонаправленный список (иметь единственную ветвь) — такое дерево может возникнуть, если элементы поступали в дерево в порядке возрастания (убывания) их ключей, например :

В этом случае время поиска будет такое же, как и в однонаправленном списке, т.е. в среднем придется перебрать N/2 элементов.
Наибольший эффект использования дерева достигается в том случае, когда дерево «сбалансировано». В этом случае для поиска придется перебрать не более LOG2N элементов.
Опишем процедуру поиска. Переменной search будет присваиваться указатель на найденное звено :
p=tree
WHILE p<>nil DO
IF key=k (p)
THEN search=p
RETURN
END IF
IF key<>k (p)
THEN p=left (p)
ELSE p=right (p)
END IF
END WHILE
search=nil
RETURN
Процедура включения элемента в дерево
Для включения новой записи в дерево прежде всего нужно найти тот его узел, к которому можно «подвесить» (присоединить) новый элемент. Алгоритм поиска нужного узла тот же самый, что и при поиске узла с заданным ключом. Этот узел будет найден в тот момент, когда в качестве очередной ссылки, определяющей ветвь дерева, в которой надо продолжить поиск, окажется ссылка NIL.

Страницы: 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

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