Бинарные деревья
Автор: spreadeagle • Январь 30, 2025 • Лабораторная работа • 1,538 Слов (7 Страниц) • 13 Просмотры
Министерство науки и высшего образования РФ
Федеральное государственное бюджетное образовательное
учреждение высшего образования
ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СИСТЕМ УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ (ТУСУР)
Кафедра автоматизированных систем управления (АСУ)
«Бинарные деревья»
Отчет по лабораторной работе № 1
Вариант № 6
по дисциплине
«Структуры и алгоритмы обработки данных на ЭВМ»
Студент группы: з-582П5-6
направления подготовки 09.03.01
А.А Кондратенко
(ИОФ)
__________________
(дата)
Проверил:
ст. преподаватель каф. КСУП ТУСУР, (ученая степень, звание)
Е.А. Потапова
(ФИО)
Томск 2022 г.
СОДЕРЖАНИЕ
- Тема работы
- Цель работы
- Индивидуальное задание
- Алгоритм решения задачи
- Результат работы программы
- Выводы
Приложение А. Листинг программы
- Литература
- Тема работы
«Бинарные дервья»
- Цель работы:
Получить практические навыки представления в памяти ЭВМ структуры данных «бинарное дерево», реализовать на языке программирования C/C++ алгоритмы работы с деревьями.
- Индивидуальное задание
Дана последовательность чисел. Построить бинарное дерево поиска, содержащее эти числа. Произвести обход дерева слева направо. После выполнения программы очистить память, занятую древовидной структурой.
- Алгоритм решения задачи
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <malloc.h>
#include <Windows.h>
Устанавливаем типы данных структуры бинарного дерева:
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);
...