Презентация Рекурсия и деревья онлайн

Содержание слайда: Рекурсия и деревья Лекция №8

Содержание слайда: Рекурсия

Содержание слайда: Линейная рекурсия Простейшим примером рекурсии является линейная рекурсия, когда функция содержит единственный условный вызов самой себя. В таком случае рекурсия становится эквивалентной обычному циклу. Действительно, любой циклический алгоритм можно преобразовать в линейно-рекурсивный и наоборот. Продемонстрируем это на примере вычисления факториала:

Содержание слайда: Рекурсия и поисковые задачи С помощью рекурсии легко решаются задачи, связанные с поиском, основанном на полном или частичном переборе возможных вариантов. Принцип рекурсивности заключается здесь в следующем: Процесс поиска разбивается на шаги; На каждом выбирается и проверяется очередной элемент из множества; Алгоритм поиска повторяется, но уже для «оставшихся» данных. При этом вовсе не важно, каким образом цепочка шагов достигнет цели и сколько вариантов будет перебираться.

Содержание слайда: Результат рекурсивной функции Если рекурсивная функция имеет результат void, то она не может повлиять на характер протекания процесса поиска и реализуемый алгоритм будет выполнять полный перебор всех возможных вариантов; Если рекурсивная функция выполняет поиск первого попавшегося варианта, то результатом ее является как правило логическое значение (в Си - 0/1). При этом «ИСТИНА» соответствует успешному завершению поиска, а «ЛОЖЬ» - неудачному. Общим для всех алгоритмов поиска является: если рекурсивный вызов возвращает «ИСТИНУ», то она должна быть немедленно «передана наверх», то есть текущий вызов также должен быть завершен со значением «ИСТИНА». Если рекурсивный вызов возвращает «ЛОЖЬ», по поиск должен быть продолжен. При завершении полного перебора всех вариантов рекурсивная функция также должна возвратить «ЛОЖЬ»; Если в процессе поиска производится более сложный анализ и сравнение вариантов, то рекурсивная функция и, соответственно, шаг процесса должны производить выбор между подходящими вариантами, в целью выбора наиболее оптимального. Обычно для этого используется минимум или максимум какой-либо характеристики выбираемого варианта. Тогда рекурсивная функция возвращает значение, которое является оценкой для оставшихся не просмотренных элементов, а текущий рекурсивный вызов выбирает из них минимум или максимум с учетом данных текущего шага.

Содержание слайда: Рекурсивная структура данных По аналогии с рекурсивным вызовом функции существуют структуры данных, допускающие рекурсивное определение: элемент структуры данных содержит один или несколько указателей на элементы такого же типа. Формально это соответствует тому факту, что в определении структурированного типа содержится указатель на себя самого. Из подобных структур данных были рассмотрены списки. Однако функции, работающие с ними, не были рекурсивными.

Содержание слайда: Деревья Определение дерева имеет исключительно рекурсивную природу. Элемент этой структуры данных называется вершиной (узлом). Дерево представляет собой либо отдельную вершину, либо вершину, имеющую ограниченное число указателей другие деревья (ветвей). Нижележащие деревья для текущей вершины называются поддеревьями, а их вершины – потомками. По отношению к потомкам текущая вершина называется предком.

Содержание слайда: Деревья

Содержание слайда: Работа с деревьями

Содержание слайда: Бинарные деревья

Содержание слайда: Бинарные деревья. Структура и обход

Содержание слайда: Добавление нового элемента в бинарное дерево

Содержание слайда: Удаление элемента из дерева

Содержание слайда: Пример. Сортировка элементов массива с помощью дерева Написать программу, подсчитывающую частоту встречаемости слов входного потока. Поскольку список слов заранее не известен, мы не можем предварительно упорядочить его. Неразумно пользоваться линейным поиском каждого полученного слова, чтобы определять, встречалось оно ранее или нет, т.к. в этом случае программа работает слишком медленно. Один из способов — постоянно поддерживать упорядоченность уже полученных слов, помещая каждое новое слово в такое место, чтобы не нарушалась имеющаяся упорядоченность. Воспользуемся бинарным  В дереве каждый узел содержит: указатель на текст слова; счетчик числа встречаемости; указатель на левого потомка; указатель на правого потомка.