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

Вставим узел с номером 150, тогда он станет  правым сыном узла с номером   120, т.к. он  является большим по значению узла с номером 120, но меньше значения узла головы дерева.

P — рабочий указатель
Q — указатель  отстающий от Р на один шаг
V — указатель на элемент, который будет вставлен в бинарное дерево .

Иллюстрация процесса вставки  узла 150, в соответствии с вышеприведенным алгоритмом (красным цветом выделены новые связи в дереве).

Конечный вариант дерева после вставки :

Программа
Псевдокод                               Паскаль
Q=nil                                  Q=nil
P=Tree                                 P=Tree
While (P<>nil) do                      While (P<>nil) do
Q=P                                  Begin
If key=k(P) then                       Q=P;
search=P                          If key=P^.k then
return                              Begin
EndIf                                    search:=P;
If key<k(P)  then                            exit;
P=left(P)                               End;
else                                   If key<P^.k then
P=right(P)                              P:=P^.left;
EndIf                                 else
EndWhile                                   P:=P^.right;
V=maketree(key,rec)                    End;
If key<k(Q) then                     V=maketree(key,rec)
else                                 If key<Q^.k then
Right(Q)=V                            Q^.left:=V
EndIf                                 else
search=V                               Q^.right:=V;
Return                                  search:=V

Задания

Используя  генератор  случайных  чисел  сформировать бинарное дерево, состоящее из  5 элементов  (предусмотреть ручной ввод элементов).  Причем числа должны лежать в диапазоне от -99 до 99. Произвести поиск с вставкой    элементов в соответствии со следующими вариантами заданий:

1. Числа кратные N.
2. Нечетные числа.
3. Числа > N.
4. Простые числа.
5. Числа по выбору.
6. Случайное число.
7. Составные числа.
8. Числа в интервале от X до Y.
9. Числа, сумма цифр (по модулю) которого > N.
10. Числа, сумма цифр (по модулю) которого < N.
11. Числа, сумма цифр (по модулю) которого лежит в интервале от X до Y.
12. Числа, взятые по модулю, квадратный корень которых целое число.
где: N, X, Y  — задается преподавателем.

Лабораторная работа № 13. «ПОИСК ПО ДЕРЕВУ С ИСКЛЮЧЕНИЕМ»

Цель работы: исследовать и изучить методы поиска с помощью дерева.

Задача работы: овладеть навыками написания программ для поиска с помощью бинарного дерева на языке программирования ПАСКАЛЬ .

Порядок работы :
изучить описание лабораторной работы;
по заданию, данному преподавателем, разработать алгоритм программы решения задачи;
написать программу на языке ПАСКАЛЬ;
отладить программу;
решить задачу;
оформить отчет.

Краткая теория