Файл: Отчет по лабораторной работе 1 Вариант 6 по ди с циплине Структуры и алгоритмы обработки данных на эвм.docx
Добавлен: 28.04.2024
Просмотров: 36
Скачиваний: 4
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
Министерство науки и высшего образования РФ
Федеральное государственное бюджетное образовательное
учреждение высшего образования
ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СИСТЕМ УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ (ТУСУР)
Кафедра автоматизированных систем управления (АСУ)
«Бинарные деревья»
Отчет по лабораторной работе № 1
Вариант № 6
по дисциплине
«Структуры и алгоритмы обработки данных на ЭВМ»
Студент группы: з-582П5-6
направления подготовки 09.03.01
А.А Кондратенко
(ИОФ)
__________________
(дата)
Проверил:
ст. преподаватель каф. КСУП ТУСУР, (ученая степень, звание)
Е.А. Потапова
(ФИО)
Томск 2022 г.
СОДЕРЖАНИЕ
-
Тема работы -
Цель работы -
Индивидуальное задание -
Алгоритм решения задачи -
Результат работы программы -
Выводы
Приложение А. Листинг программы
-
Литература
-
Тема работы
«Бинарные дервья»
-
Цель работы:
Получить практические навыки представления в памяти ЭВМ структуры данных «бинарное дерево», реализовать на языке программирования C/C++ алгоритмы работы с деревьями.
-
Индивидуальное задание
Дана последовательность чисел. Построить бинарное дерево поиска, содержащее эти числа. Произвести обход дерева слева направо. После выполнения программы очистить память, занятую древовидной структурой.
-
Алгоритм решения задачи
#include
#include
#include
#include
#include
#include
Устанавливаем типы данных структуры бинарного дерева:
typedef struct binarytree
{ int Data; //поле данных
binarytree* Left; //указатель на левого потомка
binarytree* Right; //указатель на правого потомка
} BinaryTree;
//вставкавершинывбинарноедерево
void Insert_Node_BinaryTree(BinaryTree * *Node, int Data) {
BinaryTree* New_Node = (BinaryTree*)
malloc(sizeof(BinaryTree));
New_Node->Data = Data;
New_Node->Left = NULL;
New_Node->Right = NULL;
BinaryTree** ptr = Node;//вспомогательныйуказатель
while (*ptr != NULL)
if (Data < (*ptr)->Data) ptr = &((*ptr)->Left);
else ptr = &((*ptr)->Right);
*ptr = New_Node;
}
//удаление вершины из бинарного дерева
void Delete_Node_BinaryTree(BinaryTree** Node, int Data) {
if ((*Node) != NULL) {
if ((*Node)->Data == Data) {
BinaryTree* ptr = (*Node);
if ((*Node)->Left == NULL && (*Node)->Right == NULL)
(*Node) = NULL;
else if ((*Node)->Left == NULL) (*Node) = ptr->Right;
else if ((*Node)->Right == NULL) (*Node) = ptr->Left;
else {
(*Node) = ptr->Right;
BinaryTree** ptr1;
ptr1 = Node;
while (*ptr1 != NULL)
ptr1 = &((*ptr1)->Left);
(*ptr1) = ptr->Left;
}
free(ptr);
Delete_Node_BinaryTree(Node, Data);
}
else {
Delete_Node_BinaryTree(&((*Node)->Left), Data);
Delete_Node_BinaryTree(&((*Node)->Right), Data);
}
}
}
//созданиебинарногодерева
void Create(BinaryTree** p, int x)
{
if (!(*p))//если указатель на корень дерева не равен NULL
{
BinaryTree* pnew = (BinaryTree*)malloc(sizeof(BinaryTree));// выделяем память
pnew->Data = x;//заносим значение
pnew->Left = pnew->Right = NULL;
*p = pnew;
}
else
{
if ((*p)->Data > x)
Create(&((*p)->Left), x);
else
Create(&((*p)->Right), x);
}
}
//Вывод двоичного дерева на экран
void Vyvod(BinaryTree** p, int l)
{
int i;
if (*p != NULL)
{
Vyvod(&((*p)->Right), l + 1);
for (i = 0; i < l; i++)
printf(" ");
printf("%d\n", (*p)->Data);
Vyvod(&((*p)->Left), l + 1);
}
}
//симметричный обход бинарного дерева
void SymmetricOrder_BinaryTree(BinaryTree* Node) {
if (Node != NULL) {
BinaryTree* Left;
printf("%3ld", Node->Data);
}else{
BinaryTree* Right;
}
}
//Проверка пустоты дерева
bool empty_tree(BinaryTree* Node)
{
if (Node == NULL) return true;
else return false;
}
int main()
{
SetConsoleCP(1251);
SetConsoleOutputCP(1251);
int i, n, temp;
BinaryTree* Root;
Root = NULL;
printf("Число элементов дерева\t");
scanf_s("%d", &n);
for (i = 0; i < n; i++)
{
scanf_s("%d", &temp);
Create(&Root, temp);
}
Vyvod(&Root, 0);
printf("\nВставляемый элемент\t");
scanf_s("%d", &temp);
Insert_Node_BinaryTree(&Root, temp);
Vyvod(&Root, 0);
printf("\nУдаляемый элемент\t");
scanf_s("%d", &temp);
Delete_Node_BinaryTree(&Root, temp);
if (empty_tree(Root))
{
printf("\nДерево пусто!\n");
getchar();
return 0;
}
Vyvod(&Root, 0);
printf("\nСимметричный обход бинарного дерева\n");
SymmetricOrder_BinaryTree(Root);
Root = Root;
if (empty_tree(Root))
printf("\nПамять очищена полностью!\n");
getchar();
return 0;
}
-
Результат работы программы
Заключение
Во время выполнения данной лабораторной работы, получил практические навыки представления в памяти ЭВМ структуры данных «бинарное дерево», алгоритмы работы с деревьями, создание дерева, добавление и удаления вершин.
Список используемой литературы:
Структуры и алгоритмы обработки данных в ЭВМ: учебное пособие /
И. А. Красиков. – Томск : ФДО, ТУСУР, 2016. – 252 с.
Структуры и алгоритмы обработки данных на ЭВМ: методические указания по выполнению лабораторных работ. И. А. Красиков — Томск: Факультет дистанционного обучения, ТУСУР, 2016. — 24 с.
