Вставим узел с номером 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. «ПОИСК ПО ДЕРЕВУ С ИСКЛЮЧЕНИЕМ»
Цель работы: исследовать и изучить методы поиска с помощью дерева.
Задача работы: овладеть навыками написания программ для поиска с помощью бинарного дерева на языке программирования ПАСКАЛЬ .
Порядок работы :
изучить описание лабораторной работы;
по заданию, данному преподавателем, разработать алгоритм программы решения задачи;
написать программу на языке ПАСКАЛЬ;
отладить программу;
решить задачу;
оформить отчет.
Структуры и алгоритмы обработки данных
Вставим узел с номером 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. «ПОИСК ПО ДЕРЕВУ С ИСКЛЮЧЕНИЕМ»
Цель работы: исследовать и изучить методы поиска с помощью дерева.
Задача работы: овладеть навыками написания программ для поиска с помощью бинарного дерева на языке программирования ПАСКАЛЬ .
Порядок работы :
изучить описание лабораторной работы;
по заданию, данному преподавателем, разработать алгоритм программы решения задачи;
написать программу на языке ПАСКАЛЬ;
отладить программу;
решить задачу;
оформить отчет.
Краткая теория
Страницы: 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