БІНАРНЕ ДЕРЕВО ПОШУКУ. Звіт до лабораторної роботи з Програмування Частина III Структури даних та алгоритми. Робота № 527650

БІНАРНЕ ДЕРЕВО ПОШУКУ

Інформація про навчальний заклад

ВУЗ:

Національний університет Львівська політехніка

Інститут:

Не вказано

Факультет:

КН

Кафедра:

Кафедра ЕОМ

Інформація про роботу

Рік:

2016

Тип роботи:

Звіт до лабораторної роботи

Предмет:

Програмування Частина III Структури даних та алгоритми

Завантажити

Частина тексту файла (без зображень, графіків і формул):

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА” Кафедра ЕОМ / ЗВІТ до лабораторної роботи № 6 на тему: "БІНАРНЕ ДЕРЕВО ПОШУКУ" з дисципліни: "Програмування, частина 3(Структури даних та алгоритми)" Мета роботи: Вивчення абстрактної структури даних "Бінарне дерево пошуку". Набуття практичних навичок побудови дерева та використання його для розв'язання прикладних задач. Iндивiдуальне завдання : І. Завдання 1: Побудувати бінарне дерево пошуку для послідовності чисел, що вводяться з клавіатури. Реалізувати операції додавання та вилучення вузлів з бінарного дерева пошуку. Виконати обхід дерева у заданому порядку та показати: послідовність вершин дерева при проходженні його у прямому порядку; послідовність листків дерева при проходженні його у зворотньому порядку; послідовність вузлів, що мають тільки одного нащадка при проходженні дерева у симетричному порядку. Виконати індивідуальне завдання згідно з варіантом. Варіант №6 Побудувати два бінарних дерева пошуку та визначити, чи є вони дзеркальним відображенням одне одного. ІІ. Завдання 2: Використовуючи побудоване в Завданні 1 бінарне дерево пошуку, розв'язати задачу згідно з варіантом. Варіант №4 У деякій країні поліція виявила розгалужену мережу опозиційної партії. Партія сильно законспірована і складається з рядових членів і керівників різних рівнів. На чолі партії стоїть один головний керівник - лідер партії. Всі члени партії пронумеровані від 1 до N. Кожний член партії знає тільки свого безпосереднього керівника (рівно одного) і своїх безпосередніх підлеглих (керівник не знає підлеглих свого підлеглого і навпаки). До початку арештів наказ лідера може бути доведений до будь-якого члена партії. З початком арештів членів партії вона розпадеться на дрібні, не зв'язані один з одним групи. Поліцмейстер запевняє, що група, що складається з менш ніж K членів партії, ідеологічно вироджується і не становить погрози для держави. Прагнучи не упустити престиж країни в очах світової суспільної думки, поліцмейстер поставив задачу зробити мінімальну кількість арештів членів партії так, щоб від неї залишилися тільки маленькі групи. Написати програму, яка б по вхідним даним, що знаходяться в текстовому файлі, описувала структуру підпільної партії і виводила кількість арештів і номери членів партії, яких потрібно заарештувати. При наявності декількох розв'язків вивести одне з них. Код програми: #include<iostream> using namespace std; int counter = 0; //Визначення вузла для двійкового дерева пошуку struct BstNode { int data; BstNode* left; BstNode* right; }; //Функція знайти мінімум в дереві BstNode* FindMin(BstNode* root) { while (root->left != NULL) root = root->left; return root; } // Функція пошуку i видалити значення з дерева struct BstNode* Delete(struct BstNode *root, int data) { if (root == NULL) return root; else if (data < root->data) root->left = Delete(root->left, data); else if (data > root->data) root->right = Delete(root->right, data); // Я знайшов вас, будьте готові бути видалені else { // Case 1: No child if (root->left == NULL && root->right == NULL) { delete root; root = NULL; } //Case 2: One child else if (root->left == NULL) { struct BstNode *temp = root; root = root->right; delete temp; } else if (root->right == NULL) { struct BstNode *temp = root; root = root->left; delete temp; } // case 3: 2 children else { struct BstNode *temp = FindMin(root->right); root->data = temp->data; root->right = Delete(root->right, temp->data); } } return root; } //Функція для відвідування вузлів void Inorder(BstNode *root) { if (root == NULL) return; Inorder(root->left); //Візит залишив пiддерево printf("%d ", root->data); //дані друку Inorder(root->right); // Відвідати праве піддерево } // Функція для створення нового вузла в купі BstNode* GetNewNode(int data) { BstNode* newNode = new BstNode(); newNode->data = data; newNode->left = newNode->right = NULL; return newNode; } // Щоб вставити дані в BST, повертає адресу кореневого вузла BstNode* Insert(BstNode* root, int data) { if (root == NULL) { // empty tree root = GetNewNode(data); } // якщо дані повинні бути вставлені меншу, вставте в ліве піддерево else if (data <= root->data) { root->left = Insert(root->left, data); } // ще, вставте в правому поддереве else { root->right = Insert(root->right, data); } return root; } //Для пошуку елемента в BST, повертає істину, якщо елемент знайдено bool Search(BstNode* root, int data) { if (root == NULL) { return false; } else if (root->data == data) { return true; } else if (data <= root->data) { return Search(root->left, data); } else { return Search(root->right, data); } } //Перевірте функції для дерева дзеркало bool checkMirror(BstNode* root1, BstNode* root2) { if (root1 == NULL && root2 == NULL) { return true; } if (root1->data != root2->data) { return false; } if ((root1 == NULL && root2 != NULL) || (root1 != NULL && root2 == NULL)) { // якщо вузол не має відповідного вузла в сусідній дерева, повернутися помилковим return false; } // перевірити, якщо залишити вузол в одному дереві є правильним вузол в інше дерево, і навпаки return checkMirror(root1->left, root2->right) && checkMirror(root1->right, root2->left); } //Друга функція ЗАВДАННЯ void freeBst(BstNode* t) //отримати корінь { if (t == NULL) return; if (t->left != NULL) freeBst(t->left); if (t->right != NULL) freeBst(t->right); counter++; delete t; /* free(t) if c */ } //Основна функція int main() { setlocale(LC_ALL, "ukr"); BstNode* root1 = NULL; // Створення порожнього дерева // Створення першого двійкового дерева пошуку root1 = Insert(root1, 15); root1 = Insert(root1, 10); root1 = Insert(root1, 20); root1 = Insert(root1, 25); root1 = Insert(root1, 8); root1 = Insert(root1, 12); BstNode* root2 = NULL; // Створення другого двійкового дерева пошуку root2 = Insert(root2, 25); root2 = Insert(root2, 20); root2 = Insert(root2, 30); root2 = Insert(root2, 45); root2 = Insert(root2, 85); root2 = Insert(root2, 22); // Запитати користувача, щоб ввести номер int number; cout << "Введiть число яке потршбно знайти: \n"; cin >> number; //Якщо номер знайдений, друк "ЗНАЙДЕНО" if (Search(root1, number) == true) cout << "ЗНАЙДЕНО\n" << endl; else cout << "НЕ ЗНАЙДЕНО\n" << endl; Delete(root1, number); if (Search(root1, number) == true) cout << "ЗНАЙДЕНО\n" << endl; else cout << "НЕ ЗНАЙДЕНО\n" << endl; bool mirrorChecker; mirrorChecker = checkMirror(root1, root2); if (mirrorChecker == 1) cout << "Бiнарнi дерева пошуку дзеркального" << endl; else cout << "Бiнарнi дерева пошуку НЕ дзеркального" << endl; freeBst(root1); cout << "Лiчильник: " << counter << endl; system("pause"); } Результат виконання програми : / Висновок: на лабораторній роботі №5, ознайомився зі структурою даних "Бінарне дерево пошуку".

Звіт до лабораторної роботи Програмування Частина III Структури даних та алгоритми

R.Karpyn

28.02.2016 12:59

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, або зареєструйтесь.

Ділись своїми роботами та отримуй миттєві бонуси!

поділитись