Рекурсия. Бинарные деревья

МИНОБРНАУКИ РОССИИ

Федеральное государственное бюджетное образовательное учреждение высшего образования[pic 1]

НИЖЕГОРОДСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ

УНИВЕРСИТЕТ им. Р.Е.АЛЕКСЕЕВА

 Институт радиоэлектроники и информационных технологий

Кафедра прикладной математики и информатики

Лабораторная работа №3. Рекурсия. Бинарные деревья.

ОТЧЕТ

по лабораторной работе

по дисциплине

Технология программирования

РУКОВОДИТЕЛЬ:

________________            ____________________

            (подпись)                          (фамилия, и.,о.)

СТУДЕНТ:

_______________   Фоканов Сергей Андреевич

(подпись)                 

                                 21-ПМ-2

Работа защищена «___» ____________

С оценкой ________________________

Нижний Новгород 2022

Задача 14. 

Дано бинарное дерево. Найти поддерево, не включающее ни одну из заданных вершин.

Справка:

[pic 2]

В данной работы мы использовали представление бинарного дерева в виде одномерного массива. В этом компактном расположении, если узел имеет индекс i, его дочерние элементы находятся по индексам 2i + 1 (для левого дочернего элемента) и 2i + 2 (для правого).

Описание программы:

Та часть, что непосредственно взаимодействует с бинарным деревом, можно разделить на 3 этапа.

1 этап.

Идея заключается в том, чтобы перед 2 этапом массив-бинарное дерево не включал в себя узлы, которые точно не попадут в искомое максимальное поддерево, и при этом сохранилось общее положение остальных вершин. Отметим, что, если на 1 этапе никаких изменений в массиве не произойдёт, это будет значить следующее: всё бинарное дерево есть решение задачи.

Для более детального ознакомления с работой всех алгоритмов, пожалуйста, смотрите комментарии к коду.