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

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

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

высшего профессионального образования

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

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

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

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

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

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

Выполнил студент:

Шкодин Александр Леонидович

специальности 09.03.01

гр. з-439П2-5 

«  11  »   августа   2019г.

Проверил:

«      »                         2019г.

2019г.

СОДЕРЖАНИЕ

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

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

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

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

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

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

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

1. Тема работы: «Бинарные деревья».

1. Цель работы: Получить практические навыки представления в памяти ЭВМ структуры данных «бинарное дерево», реализовать на языке программирования C/C++ алгоритмы работы с деревьями.

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

Вариант № 4

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

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

1.          Первоначально определяемся с примерным решением задачи и подключаем необходимые нам библиотеки;
2.          Создаем тип элемента и объявляем структуру необходимую нам для решения задачи (в нашем случае поузловую структуру дерева);
3.          Объявляем необходимые функции для решения задачи (функция выделения памяти для нового узла и вставки его в дерево-ode* insertNode(T data), функцию удаления узла из дерева void deleteNode(Node *z), функция поиска узла, содержащего необходимые нам данные Node* findNode(T data), а также функцию вывода бинарного дерева void printTree(Node *node, int l));

После объявления функций описываем алгоритм работы этих функций;

1.          Для реализации наших функций создаем главную функцию программы main.

В функции main мы реализуем следующие шаги:

-SetConsoleCP(1251); задаем кодировку для вывода символов на экран;

-SetConsoleOutputCP(1251); задаем кодировку для ввода символов с клавиатуры в консоль;

-Задаем целочисленные вспомогательные переменные int;

-По условию задачи создаем две последовательности чисел (используя рандомное генерирование чисел rand());

-Из первой последовательности чисел с помощью функции

insertNode создаем бинарное дерево;

- С помощью функции printTree выводим созданное дерево;

-Используя функцию findNode ищем числа первой последовательности входящие в бинарное дерево;

-Проводим удаление бинарного дерева из памяти с помощью функции deleteNode.

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

[pic 1]

[pic 2]

[pic 3]

1. Выводы:

В результате выполнения лабораторной работы №1 мы получили теоретический материал по теме бинарные деревья, отработали практические навыки реализации бинарного дерева на языке Си. Рассмотрели и провели основные операции:

-поиск вершины;

-добавление вершины;

-вывод (печать) дерева;