БИНАРНЫЕ ДЕРЕВЬЯ Отчёт по лабораторной работе №1 по дисциплине «Структуры и алгоритмы обработки данных на ЭВМ». Лаб.работа №1. Управления и радиоэлектроники (тусур) бинарные деревья
 Скачать 63.57 Kb.
|
|
Министерство науки и высшего образования Российской Федерации Федеральное государственное бюджетное образовательное учреждение высшего образования ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СИСТЕМ УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ (ТУСУР) БИНАРНЫЕ ДЕРЕВЬЯ Отчёт по лабораторной работе №1 по дисциплине «Структуры и алгоритмы обработки данных на ЭВМ» Студент гр. з-431П10-5 Иван Михайлович Пивоваров Направления подготовки 09.03.01 Вариант №2 «14» февраля 2021 г. Проверил: Старший преподаватель каф. КСУП Е.И. Потапова «__»___________2021 г. 2021 ЛАБОРАТОРНАЯ РАБОТА № 1 «БИНАРНЫЕ ДЕРЕВЬЯ» Цель лабораторной работы – получить практические навыки представления в памяти ЭВМ структуры данных «бинарное дерево», реализовать на языке программирования C/C++ алгоритмы работы с деревьями. Индивидуальное задание: Дана последовательность чисел. Построить бинарное дерево, содержащее эти числа. Произвести обход дерева слева направо и вывести результаты на экран. После выполнения программы очистить память, занятую древовидной структурой. Алгоритм решения задачи Каждая вершина дерева описывается как структура, содержащая три поля: ключ и два ссылочных поля для адресации потомков: Для обработки дерева достаточно знать адрес корневой вершины. Для хранения этого адреса надо ввести ссылочную переменную, пустое дерево определяется установкой переменной root в NULL. Добавление в дерево – сначала задается корень (left, right принимают значение NULL), затем следующее добавляемое значение сравнивается с ключом корня и присваивается либо левой ветви дерева, либо правой. Дальнейшие значения добавляются к соответствующему узлу дерева. Добавление ключа в дерево: если дерево пустое выделяем память под узел задаем информационную часть узла задаем пустые ссылки на потомков выходим из добавления ключа иначе если новый ключ<ключа текущей вершины вызываем процедуру добавления для левого потомка иначе вызываем процедуру добавления для правого потомка Бинарное дерево можно определить как конечное множество узлов, которое может быть либо пустым, либо состоит из корня и двух непересекающихся бинарных деревьев (левого и правого поддеревьев), причем, каждое поддерево, в свою очередь, имеет такую же структуру. Поэтому для обхода дерева подходит рекурсивная реализация, в которой в качестве формального параметра берется корень дерева. Корень дерева при обходе слева направо проходится после того, как будут пройдена вся левая ветвь дерева до конца, затем будет пройдена правая ветвь. Алгоритм обхода слева направо: рекурсивно обработать левое поддерево текущего поддерева вывести значение вершины текущего поддерева рекурсивно обработать правое поддерево Результаты работы программы  Выводы В процессе выполнения лабораторной работы были реализованы рекурсивные процедуры добавления ключа в бинарное дерево, обхода бинарного дерева слева направо, очистки дерева после завершения работы программы. Приложение А. Листинг программы #include #include #include #include #include #include typedef struct btree //определяем структуру бинарного дерева { int value; struct btree* left, * right; } Tree; Tree* root; void Ins_Btree(int val, Tree** q) //добавление в дерево { if (*q == NULL) {//создание узла дерева *q = new Tree; (*q)->left = (*q)->right = NULL; (*q)->value = val; return; } //добавляем в существующее дерево if ((*q)->value > val) //если новый ключ меньше корня, то переходим к добавлению в левую часть { Ins_Btree(val, &(*q)->left); } else //иначе переходим на правую ветку { Ins_Btree(val, &(*q)->right); } } void Print_Btree(Tree* p)//preorder //обход дерева в прямом порядке { if (p == NULL) return; printf("%d ", p->value); Print_Btree(p->left); Print_Btree(p->right); } void Inorder(Tree* p) //обход дерева в симметричном порядке { if (p == NULL) return; Inorder(p->left); printf("%d ", p->value); Inorder(p->right); } void ReverseInorder(Tree* p) //обход дерева в обратно-симметричном порядке { if (p == NULL) return; ReverseInorder(p->right); printf("%d ", p->value); ReverseInorder(p->left); } bool emptyTree(Tree* p) { return (p == NULL ? true : false); } Tree* Find(struct btree* p, const int x) //поиск по ключу { if (!p) return NULL; //ключ не найден else if (x < p->value) //ключ меньше рассматриваемого значения – return Find(p->left, x); //переход на левую ветвь else if (x > p->value) //ключ больше рассматриваемого значения – return Find(p->right, x); //переход на правую ветвь else return p; //ключ найден } //освобождение памяти, выделенной под бинарное дерево Tree* DeleteBinaryTree(Tree *p) { if (p) { if (p->left) DeleteBinaryTree(p->left); if (p->right) DeleteBinaryTree(p->right); p = NULL; } return p; } //--------------------------------------------------- int main() { setlocale(LC_ALL, "rus"); // корректное отображение Кириллицы printf("\nБинарное дерево поиска"); //int d[] = { 45,30,55,25,35,53,60,8,32,37,65,15,34,33,40,0 }, i = 0; int key; char ch; puts("\nВвод элементов дерева (конец ввода - 0)"); do //ввод с клавиатуры элементов дерева { printf("\nВведите число:"); scanf_s("%d", &key); //считываем ключ с клавиатуры if (key == 0)break;//если конец последовательности Ins_Btree(key, &root);//добавляем в дерево } while (key != 0); //пока не введен 0 printf("\n"); printf("\nКорень дерева:"); printf("%d ", root->value,"\n"); printf("Вывод в прямом порядке:\n"); //вывод в прямом порядке Print_Btree(root); printf("\nВывод в симметричном порядке (слева направо):"); //вывод в симметричном порядке printf("\n"); Inorder(root); printf("\n"); root = DeleteBinaryTree(root); if (emptyTree(root)) printf("\nПамять очищена полностью!\n"); printf("Нажмите любую клавишу на клавиатуре для выхода из программы \n"); //std::cin>>ch; _getch(); return 0; } |