Алгоритм на псевдокоде

Сумма (p: pVertex)

IF (p = NIL) Сумма := 0

ELSE Сумма:= p→Data + Сумма(p→Left) + Сумма(p→Right )

FI

9.4 Варианты заданий

Разместить в памяти компьютера данное двоичное дерево (см. ниже), данные в вершинах заполнить случайными числами. Написать процедуры для вычисления размера дерева, высоты дерева, средней высоты дерева, контрольной суммы для дерева и проверить их работу на конкретном примере. Запрограммировать обход двоичного дерева слева направо и вывести на экран получившуюся последовательность данных.

10. Деревья поиска

10.1 Поиск в дереве

Двоичные деревья часто употребляются для представления множества данных, среди которых идет поиск элементов по уникальному ключу. Будем считать, что

1) часть данных, хранящихся в каждой вершине дерева, является ключом для поиска.

2) Для всех ключей определены операции сравнения <, >, =.

3) В дереве нет элементов с одинаковыми ключами.

Двоичное дерево называется деревом поиска, если ключ в каждой его вершине больше ключа любой вершины в левом поддереве и меньше ключа любой вершины в правом поддереве. Пример такого дерева приведен на рисунке.

Рисунок 29 Дерево поиска

Чтобы определить является ли двоичное дерево деревом поиска приведем описание на псевдокоде следующей функции. Функция возвращает значение ИСТИНА в случае, если дерево является деревом поиска, и значение ЛОЖЬ в противном случае.