Отчет. Бинарные деревья

• Название: Бинарные деревья
• Дата: 14.03.2022
• Размер: 197.17 Kb.
• Имя файла: Отчет.docx
• Тип: Отчет; #396506

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

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

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

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

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

Отчет по лабораторной работе № 1 по дисциплине «Структуры и алгоритмы обработки данных на ЭВМ

Выполнил: студент Горбенко

Анастасия Сергеевна

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

09.02.2022г

Проверил: ________________ _________________________

«____» _____________ 20__ г.

Томск – 2022

СОДЕРЖАНИЕ

1.Тема работы 2

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

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

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

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

6.Выводы 5

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

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

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

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

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

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

Вариант № 9

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

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

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

2. Для каждого введенного пользователем с клавиатуры узла с помощью процедуры Create(&Root,temp) выполнить рекурсивно поиск места, в которое можно добавить новый узел дерева и добавить его (предварительно выделив память под добавляемый узел).

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

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

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

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

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

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

9. С помощью функции empty_tree(Root) проверить дерево на пустоту, через значение самого указателя на дерево (что необходимо выполнить после полного удаления дерева из памяти).

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

Следующие изображения демонстрируют работу программы. На первом введена последовательность чисел, в том числе ноль и отрицательное число. На втором в программу введено одно число, которое затем удаляется, и, как и должно быть, дерево остается пустым. На третьем в программу вводится 0 элементов, т.е. дерево изначально пустое.

6. Выводы

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

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

#include

#include

#include

#include

#include
typedef struct binarytree

{

int Data; //поле данных

binarytree * Left; //указатель на левого потомка

binarytree * Right; //указатель на правого потомка

} BinaryTree;
//удаление вершины из бинарного дерева

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
printf(" ");

printf("%d\n",(*p)->Data);

Vyvod (&((*p)->Left),l+1);

} }
/*Проверка пустоты дерева*/

bool empty_tree(BinaryTree * Node)

{

if(Node==NULL) return true;

else return false;

}
//освобождение памяти, выделенной под бинарное дерево

BinaryTree* Delete_BinaryTree(BinaryTree* Node){

if (Node != NULL)

{

Delete_BinaryTree(Node->Left);

Delete_BinaryTree(Node->Right);

free(Node);

}

return NULL;

}
int main() {

SetConsoleCP(1251);

SetConsoleOutputCP(1251);

int i,n,temp;

BinaryTree * Root;

Root=NULL;

printf("Число элементов дерева\t"); scanf("%d",&n);

for(i=0;i
{

scanf("%d",&temp);

Create(&Root,temp);

}

printf("Двоичное дерево: \n");

Vyvod(&Root,0);

printf("\nУдаляемый элемент\t"); scanf("%d",&temp);

Delete_Node_BinaryTree(&Root,temp);

if(empty_tree(Root))

{

printf("\nДерево пусто!\n");

getch();

return 0;

}

printf("Двоичное дерево: \n");

Vyvod(&Root,0);

Root=Delete_BinaryTree(Root);

if(empty_tree(Root))

printf("\nПамять очищена полностью!\n");

getch();

return 0; }