Задания для самопроверки

Задание 1. Разработайте рекурсивную подпрограмму, осуществляющую поиск выхода из лабиринта по методу перебора с отсечением неперспективных направлений. Лабиринт представляет собой двумерный массив, в котором наличие прохода отмечено единицей, а тупик – нулем.

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

Использование рекурсии при обработке бинарных деревьев

Понятие бинарного дерева

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

Таким образом, каждая вершина бинарного дерева может включать одно или два поддерева или не включать поддеревьев вовсе. Первое поддерево обычно называют левым, а второе – правым. Соответственно ветвь, исходящую из вершины и ведущую в корень левого поддерева, называют левой, а ветвь, ведущую в корень правого поддерева – правой. Вершины, из которых не выходит ни одной ветви, называют листьями (см. рисунок 15).

Рисунок 15 - Пример бинарного дерева

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

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

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

Основные операции с сортированными бинарными деревьями:

· Построение бинарного дерева

· Обход дерева

· Поиск вершины в бинарном дереве

· Удаление вершины в бинарном дереве