2015-01-30
542
Сумма (p: pVertex)
IF (p = NIL) Сумма:= 0
ELSE Сумма:= p→Data + Сумма(p→Left) + Сумма(p→Right)
FI
9.4 Варианты заданий
Разместить в памяти компьютера данное двоичное дерево (см. ниже), данные в вершинах заполнить случайными числами. Написать процедуры для вычисления размера дерева, высоты дерева, средней высоты дерева, контрольной суммы для дерева и проверить их работу на конкретном примере. Запрограммировать обход двоичного дерева слева направо и вывести на экран получившуюся последовательность данных.
 |  | |||||||||||
 |  |  | ||||||||||
 | ||||||||||||
 | ||||||||||||
 | ||||||||||||
 | ||||||||||||
10. Деревья поиска
10.1 Поиск в дереве
Двоичные деревья часто употребляются для представления множества данных, среди которых идет поиск элементов по уникальному ключу. Будем считать, что
1) часть данных, хранящихся в каждой вершине дерева, является ключом для поиска.
2) Для всех ключей определены операции сравнения <, >, =.
|
|
|
3) В дереве нет элементов с одинаковыми ключами.
Двоичное дерево называется деревом поиска, если ключ в каждой его вершине больше ключа любой вершины в левом поддереве и меньше ключа любой вершины в правом поддереве. Пример такого дерева приведен на рисунке.
 |
Рисунок 29 Дерево поиска
Чтобы определить является ли двоичное дерево деревом поиска приведем описание на псевдокоде следующей функции. Функция возвращает значение ИСТИНА в случае, если дерево является деревом поиска, и значение ЛОЖЬ в противном случае.
