Бинарные деревья

Министерство науки и высшего образования Российской Федерации

Федеральное государственное бюджетное учреждение

высшего образования

ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СИСТЕМ

УПРАВЛЕНИЯ И РАДИОЭЛЕТРОНИКИ (ТУСУР)

Кафедра автоматизированных систем управления (АСУ)

«БИНАРНЫЕ ДЕРЕВЬЯ»

Отчет по лабораторной работе №1 по дисциплине

«Структуры и алгоритмы обработки данных на ЭВМ»

Выполнил: Беспалов Т. А.

 «___» __________ 20__ г.

Проверил: Потапова Е.А. 

«___» __________ 20__ г.

Томск – 2022

СОДЕРЖАНИЕ

1.Тема работы…………………………………………………………………………………….3

2. Цель работы……………………………………………………………………………………3

3. Индивидуальное задание……………………………………………………………………..3

4. Алгоритм решения задачи……………………………………………………………………4

5.Результат работы программы…………………………………………………………………5

6.Вывод…………………………………………………………………………………………...7

Приложение А. Листинг программы…………………………………………………………...8

Тема работы

Бинарное дерево

Цель работы

Изучить структуру и особенности доступа к данным и работы с памятью бинарных деревьев, получить практические навыки и знания представления в памяти ЭВМ структуры данных, а также реализовать структуру данных «бинарное дерево» на языке программирования C/C++ алгоритмы работы с деревьями. Научиться решать задачи с использованием рекурсивных функций и алгоритмов обхода бинарных деревьев в языке Си.

Индивидуальное задание

Вариант № 9. Дана последовательность чисел. Построить бинарное дерево, содержащее эти числа. Удалить из дерева число, введённое с клавиатуры, и вывести оставшиеся числа в дереве. После выполнения программы очистить память, занятую древовидной структурой.

Работа выполнена в Microsoft Visual Studio Community 2022 (64-разрядная версия) – Current Версия 17.1.6

Алгоритм решения задачи

Данная программа выполняет следующие действия:

1. Запрашивает у пользователя количество элементов дерева.

2. Для каждого введенного пользователем с клавиатуры узла программа с помощью процедуры Create(&Root,temp) (строка №102) выполняет рекурсивно поиск места, в которое можно добавить новый узел дерева и добавляет его (предварительно выделив память под добавляемый узел).Программа смотрит если указатель на корень дерева не равен NULL строка (строка №43) тогда мы заносим значение введенное пользователем в DATE (строка №47) и приравниваем LEFT RIGHT к NULL (строка №48) а если указать корня дерева равен NULL тогда мы смотрим наше значение DATE  и если оно значение которое указанно пользователем (строка №53) то  в указатель LEFT если меньше то RIGHR.

3. С помощью процедуры Vyvod(&Root,0) (строка №104) программа выводит содержимое дерева на экран.

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

5. С помощью процедуры Delete_Node_BinaryTree(&Root, temp) (строка №106) программа ищет элемент в дереве, который нужно удалить, сравнивая его значение со значением ключевого поля каждого имеющегося элемента дерева. Таким образом, программа ищет удаляемый  элемент в дереве, находит его и удаляет, освобождая память, занимаемую данным элементом.

6. С помощью функции empty_tree(Root)  (строка №107) программа проверяет: не пусто ли дерево? Если функция empty_tree(Root) вернула значение true, то дерево пусто (на данном этапе программы такое возможно, скорее всего, если изначально пользователь ввел количество элементов дерева, равное нулю), и работа программы завершается.

7. С помощью процедуры Vyvod(&Root,0) (строка №113) программа выводит содержимое дерева на экран, таким образом, мы можем заметить, что элемент был удален из дерева.

8. С помощью функции Delete_BinaryTree(Root) (строка №114)программа рекурсивно выполняет очистку памяти, занимаемой деревом, используя функцию освобождения памяти free. После прохождения по всем элементам дерева программа возвращает указателю на корень дерева Root значение NULL, таким образом стирая и сам указатель на это дерево.