5 практика
.pdfМинистерство науки и высшего образования Российской Федерации Федеральное государственное бюджетное образовательное учреждение высшего образования
ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СИСТЕМ УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ (ТУСУР)
Кафедра комплексной информационной безопасности электронно-
вычислительных систем (КИБЭВС)
БИНАРНЫЕ ДЕРЕВЬЯ ПОИСКА Отчет по практической работе №5 по дисциплине «Структуры данных»
Студент гр. 711-2
_______ Е. П. Толстолес
_______
Принял:
преподаватель КИБЭВС
_______ Н.С. Репьюк
_______
Томск 2022
СОДЕРЖАНИЕ:
1Введение……………………………………………………………...………….3
2Ход работы………………………………………………………………………4
2.1Реализация бинарного дерева…………………………………………...4
3Заключение…………………………………………………………………..…..7
Приложение А…………………………………………………………………..…8
2
1 Введение
Цель работы: познакомиться с бинарными деревьями поиска, написать функции для работы с ними и реализовать программу, которая выполняет необходимые действия из задания.
3
2Ход работы
2.1Реализация бинарного дерева
Двоичное дерево поиска (англ. binary search tree, BST) — это двоичное дерево, для которого выполняются следующие дополнительные условия
(свойства дерева поиска):
1)Оба поддерева — левое и правое — являются двоичными деревьями поиска.
2)У всех узлов левого поддерева произвольного узла X значения ключей данных меньше, нежели значение ключа данных самого узла X.
3)У всех узлов правого поддерева произвольного узла X значения ключей данных больше либо равны, нежели значение ключа данных самого узла X.
В ходе работы мы знакомились с тем, как устроено бинарное дерево поиска, и как работать с указателями в данной структуре данных, на рисунках
2.1 и 2.2 представлен результат выполнения программы, в которой реализованы функции из задания.
4
Рисунок 2.1 – Результат работы программы (часть 1)
5
Рисунок 2.2 – Результат работы программы (часть 2)
6
3 Заключение
Приобретены знания и опыт работы с бинарными деревьями поиска,
написаны функции для работы с ними и реализована программа, которая выполняет необходимые действия из задания.
Отчет был составлен согласно ОС ТУСУР 2021.
7
Приложение А
(обязательное)
Листинг программы
#include <stdio.h> #include <stdlib.h> #include <stdbool.h> #include <assert.h>
// Структура для хранения узла дерева. typedef struct node
{
int value;
struct node *left; struct node *right; struct node *parent;
}
node;
// Структура для хранения дерева. typedef struct tree
{
struct node *tmp;
8
struct node *root;
int numbers;
}
tree;
// Инициализация дерева void init(tree* t)
{
t->root=NULL;
}
//Функция рекурсивного удаления node* cleant(node* t)
{
if(t!=NULL)
{
cleant(t->left); cleant(t->right); if(t->parent!=NULL)
t->parent = NULL;
9
if(t->left!=NULL) t->left = NULL;
if(t->right!=NULL) t->right = NULL;
free(t);
}
return NULL;
}
// Удалить все элементы из дерева void clean(tree* t)
{
node* root = t->root; cleant(root);
t->root = NULL;
}
// Поиск элемента по значению. Вернуть NULL если элемент не найден node* find(tree* t, int value)
{
t->tmp = t->root; while(t->tmp->value != value)
10