Бинарные деревья
Автор: Shkid82 • Июль 12, 2020 • Лабораторная работа • 1,646 Слов (7 Страниц) • 515 Просмотры
Министерство образования и науки Российской Федерации
Федеральное государственное образовательное учреждение
высшего профессионального образования
«ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
СИСТЕМ УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ» (ТУСУР)
Кафедра автоматизированных систем управления (АСУ)
БИНАРНЫЕ ДЕРЕВЬЯ
Отчет по лабораторной работе №1 по дисциплине
«Структуры и алгоритмы обработки данных в ЭВМ»
Выполнил студент:
Шкодин Александр Леонидович
специальности 09.03.01
гр. з-439П2-5
« 11 » августа 2019г.
Проверил:
« » 2019г.
2019г.
СОДЕРЖАНИЕ
1. Тема работы…...…………………………………………………….……3
2. Цель работы……..…………………………………………………......…3
3. Индивидуальное задание………………………………………………...3
4. Алгоритм решения задачи………………………………………………3
5. Результаты работы программы...………………………………..………5
6. Выводы………………...…………………………………………....……6
Приложение А. Листинг программы…………………………………...…8
- Тема работы: «Бинарные деревья».
- Цель работы: Получить практические навыки представления в памяти ЭВМ структуры данных «бинарное дерево», реализовать на языке программирования C/C++ алгоритмы работы с деревьями.
- Индивидуальное задание:
Вариант № 4
Даны две последовательности чисел. Построить бинарное дерево, содержащее числа первой последовательности. Для каждого числа второй последовательности узнать, входит ли оно в дерево. После выполнения программы очистить память, занятую древовидной структурой.
- Алгоритм решения задачи:
- Первоначально определяемся с примерным решением задачи и подключаем необходимые нам библиотеки;
- Создаем тип элемента и объявляем структуру необходимую нам для решения задачи (в нашем случае поузловую структуру дерева);
- Объявляем необходимые функции для решения задачи (функция выделения памяти для нового узла и вставки его в дерево-ode* insertNode(T data), функцию удаления узла из дерева void deleteNode(Node *z), функция поиска узла, содержащего необходимые нам данные Node* findNode(T data), а также функцию вывода бинарного дерева void printTree(Node *node, int l));
После объявления функций описываем алгоритм работы этих функций;
- Для реализации наших функций создаем главную функцию программы main.
В функции main мы реализуем следующие шаги:
-SetConsoleCP(1251); задаем кодировку для вывода символов на экран;
-SetConsoleOutputCP(1251); задаем кодировку для ввода символов с клавиатуры в консоль;
-Задаем целочисленные вспомогательные переменные int;
-По условию задачи создаем две последовательности чисел (используя рандомное генерирование чисел rand());
-Из первой последовательности чисел с помощью функции
insertNode создаем бинарное дерево;
- С помощью функции printTree выводим созданное дерево;
-Используя функцию findNode ищем числа первой последовательности входящие в бинарное дерево;
-Проводим удаление бинарного дерева из памяти с помощью функции deleteNode.
- Результаты работы программы:
[pic 1]
[pic 2]
[pic 3]
- Выводы:
В результате выполнения лабораторной работы №1 мы получили теоретический материал по теме бинарные деревья, отработали практические навыки реализации бинарного дерева на языке Си. Рассмотрели и провели основные операции:
-поиск вершины;
-добавление вершины;
-вывод (печать) дерева;
...