Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
БІНАРНЕ ДЕРЕВО ПОШУКУ
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
КН
Кафедра:
Кафедра ЕОМ
Інформація про роботу
Рік:
2015
Тип роботи:
Звіт до лабораторної роботи
Предмет:
Програмування Частина 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, ознайомився зі структурою даних "Бінарне дерево пошуку".
28.02.2016 12:02-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора