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

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

Цель работы: исследовать и изучить методы поиска с помощью дерева. Задача работы: овладеть навыками написания программ для поиска с помощью бинарного дерева на языке программирования ПАСКАЛЬ . Порядок работы : изучить описание лабораторной работы; по заданию, данному преподавателем, разработать алгоритм программы решения задачи; написать программу на языке ПАСКАЛЬ; отладить программу; решить задачу; оформить отчет. Краткая теория Удаление узла дерева не должно нарушать упорядоченность дерева. При удалении возможны следующие варианты расположения узлов: найденный узел является листом - он просто удаляется (рис.1); найденный узел имеет только сына - в этом случае сын перемещается на место удаленного отца (рис.2); у удаляемого отца два сына - в этом случае основная трудность состоит в удалении отца, поскольку в удаляемую вершину входит одна стрелка, а выходит две. В этом случае нужно найти подходящее звено поддерева, которое можно было бы вставить на место удаляемого, причем это подходящее звено должно просто перемещаться. Об этом говорит сайт https://intellect.icu . Такое звено всегда существует: - это самый правый элемент левого поддерева (для достижения этого звена необходимо перейти в следующую вершину по левой ветви, а затем переходить в очередные вершины только по правой ветви до тех пор, пока очередная ссылка не будет равна nil);  - это самый левый элемент правого поддерева (для достижения этого звена необходимо перейти в следующую вершину по правой ветви, а затем переходить в очередные вершины только по левой ветви до тех пор, пока очередная такая ссылка не будет равна nil).  Очевидно, что такие подходящие звенья могут иметь не более одной ветви. Алгоритм Рассмотрим алгоритм в котором вместо удаляемого узла ставится самый левый узел правого поддерева. Удалим узел с номером 150, тогда на его место станет элемент под номером 152, т.к. он является самым левым из правого поддерева. Введем следующие обозначения: P - рабочий указатель Q - указатель отстающий от Р на один шаг V - указатель на элемент, который будет замещать удаляемый узел T - указатель, отстает от V на один шаг S - указатель, опережает V на один шаг Пример программы удаления элементов бинарного дерева (Псевдокод) Q=nil P=Tree While (P<>nil)and(K(P)<>key)do {поиск узла с нужным ключем} If key<k(p) then="" p="Left(P)<br">  Else P=Right(P) EndIf EndWhile If P=nil then "Ключ не найден" {проверка если такого элемента нет} Return {выход} EndIf If Left(P)=nil then V=Right(P) {если левая ссылка равна nil Else If Right(P)=nil then V=Left(P) Else GetNode(P) T=P V=Right(P) S = Left(V) While S <> nil {поиск самого } T = V {левого эл-нта} V = S {правого поддерева} S = Left(V) EndWhile If T <> P then "V-не сын" Left(T) = Right(V) Right(V)= Right(P) EndIf Left(V) = Left(P) If Q = nil then "p - корень" Tree = V Return EndIf If P = Left(Q) then Left(Q) = V Else Right(Q)= V EndIf EndIf EndIf FreeNode(P) Return Иллюстрация процесса удаления узла 150, в соответствии с вышеприведенным алгоритмом (красным цветом выделены новые связи в дереве). Конечный вариант дерева после удаления

Задания

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

1. Числа кратные N.

2. Нечетные числа.

3. Числа > N.

4. Числа < N.

5. Числа по выбору.

6. Простые числа.

7. Составные числа.

8. Числа в интервале от X до Y.

9. Числа, сумма цифр (по модулю) которого > N.

10. Числа, сумма цифр (по модулю) которого < N.

11. Числа, сумма цифр (по модулю) которого лежит в интервале от X до Y.

12. Числа, взятые по модулю, квадратный корень которых целое число.

где: N, X, Y - задается преподавателем.

На этом все! Теперь вы знаете все про поиск по дереву с исключением, Помните, что это теперь будет проще использовать на практике. Надеюсь, что теперь ты понял что такое поиск по дереву с исключением и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Структуры данных

Из статьи мы узнали кратко, но содержательно про поиск по дереву с исключением