Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Лабораторна робота №7 Програмування, ч3
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Кафедра ЕОМ
Інформація про роботу
Рік:
2017
Тип роботи:
Лабораторна робота
Предмет:
Програмування алгоритмів цифрової обробки сигналів та зображень
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
/
Кафедра ЕОМ
Структура даних
"БІНАРНЕ ДЕРЕВО ПОШУКУ"
ЗВІТ
до лабораторної роботи № 7
з
"Програмування. Частина III.
Структури даних та алгоритми"
МЕТА РОБОТИ
Вивчення фундаментальної абстрактної структури даних - черги. Набуття практичних навичок побудови черги, дослідження динаміки її вмісту та використання черг для розв'язання прикладних задач.
ВИБІР ІНДИВІДУАЛЬНОГО ЗАВДАННЯ
І. Завдання 1: Побудувати бінарне дерево пошуку для послідовності чисел, що вводяться з клавіатури. Реалізувати операції додавання та вилучення вузлів з бінарного дерева пошуку. Виконати обхід дерева у заданому порядку та показати:
послідовність вершин дерева при проходженні його у прямому порядку;
послідовність листків дерева при проходженні його у зворотньому порядку;
послідовність вузлів, що мають тільки одного нащадка при проходженні дерева у симетричному порядку.
Виконати індивідуальне завдання згідно з варіантом.
П, 6.02
Перша літера прізвища студента
День народження студента
Варіант
А, І, С
Б, Ї, Т
В, Й, У
Г, К, Ф
Д, Л, Х
Е, М, Ц
Є, Н, Ч
Ж,О,Ш,Щ
З, П, Ю
И, Р, Я
1, 11, 21
І 1
І 2
І 3
І 4
І 5
І 6
І 7
І 8
І 9
І 10
2, 12, 22
І 10
І 11
І 12
І 13
І 14
І 15
І 16
І 17
І 17
І 19
3, 13, 23
І 9
І 10
І 1
І 2
І 3
І 4
І 5
І 6
І 7
І 8
4, 14, 24
І 10
І 11
І 12
І 13
І 14
І 15
І 16
І 17
І 18
І 19
5, 15, 25
І 7
І 8
І 9
І 10
І 1
І 2
І 3
І 4
І 5
І 6
6, 16, 26
І 6
І 7
І 8
І 9
І 10
І 1
І 2
І 3
І 13
І 5
7, 17, 27
І 15
І 16
І 17
І 18
І 19
І 20
І 11
І 12
І 4
І 14
8, 18, 28
І 4
І 5
І 6
І 7
І 8
І 9
І 10
І 1
І 2
І 3
9, 19, 29
І 13
І 14
І 15
І 16
І 17
І 18
І 19
І 20
І 11
І 12
10, 20, 30
І 2
І 3
І 4
І 5
І 6
І 7
І 8
І 9
І 10
І 1
13. Визначити, чи побудоване дерево є повним деревом.
Код програми
Tree.h
#pragma once
#pragma once
#include <iostream>
using namespace std;
#define T int
class BSTree
{
private:
struct node {
T data;
node *left;
node *right;
};
node* root;
node* CreateLeaf(T);
bool varIsFull = true;
void AddLeafPrivate(T, node*);
void PrintInOrderPrivate(node*);
void PrintPreorderPrivate(node*);
void PrintPostorderPrivate(node*);
node* ReturnNode(T, node*);
T FindSmallestPrivate(node*);
void RemoveNodePrivate(T, node*);
void RemoveRootMatch();
void RemoveMatch(node*, node*, bool);
void isFullPrivate(node*);
void RemoveTree(node*);
public:
BSTree();
~BSTree();
void AddLeaf(T);
void PrintInOrder();
void PrintPreorder();
void PrintPostorder();
T ReturnRootData();
void PrintChildren(T);
T FindSmallest();
void RemoveNode(T);
bool isFull();
};
Tree.cpp
#include "Tree.h"
BSTree::BSTree()
{
root = NULL;
}
BSTree::~BSTree()
{
RemoveTree(root);
}
BSTree::node* BSTree::CreateLeaf(T data)
{
node* n = new node;
n->data = data;
n->left = NULL;
n->right = NULL;
return n;
}
void BSTree::AddLeaf(T data)
{
AddLeafPrivate(data, root);
}
void BSTree::AddLeafPrivate(T data, node* Ptr)
{
if (root == NULL)
root = CreateLeaf(data);
else if (Ptr->data > data) {
if (Ptr->left != NULL)
AddLeafPrivate(data, Ptr->left);
else
Ptr->left = CreateLeaf(data);
}
else if (Ptr->data < data) {
if (Ptr->right != NULL)
AddLeafPrivate(data, Ptr->right);
else
Ptr->right = CreateLeaf(data);
}
else
{
cout << "The data " << data << " has already been added to the the tree.\n";
}
}
void BSTree::PrintInOrder()
{
PrintInOrderPrivate(root);
cout << endl;
}
void BSTree::PrintInOrderPrivate(node* Ptr)
{
if (Ptr == NULL) return;
//PrintInOrderPrivate(Ptr->left);
//cout << Ptr->data << ' ';
//PrintInOrderPrivate(Ptr->right);
if (root != NULL)
{
if (Ptr->left != NULL)
PrintInOrderPrivate(Ptr->left);
if (Ptr->left == NULL && Ptr->right != NULL || Ptr->left != NULL && Ptr->right == NULL)
cout << Ptr->data << ' ';
if (Ptr->right != NULL)
PrintInOrderPrivate(Ptr->right);
}
else cout << "The tree is empty\n";
}
void BSTree::PrintPreorder()
{
PrintPreorderPrivate(root);
cout << endl;
}
void BSTree::PrintPreorderPrivate(node* Ptr)
{
if (Ptr == NULL) return;
cout << Ptr->data << ' ';
PrintPreorderPrivate(Ptr->left);
PrintPreorderPrivate(Ptr->right);
}
void BSTree::PrintPostorder()
{
PrintPostorderPrivate(root);
cout << endl;
}
void BSTree::PrintPostorderPrivate(node* Ptr)
{
if (Ptr == NULL) return;
PrintPostorderPrivate(Ptr->left);
PrintPostorderPrivate(Ptr->right);
if (Ptr->left == NULL && Ptr->right == NULL)
cout << Ptr->data << ' ';
}
BSTree::node* BSTree::ReturnNode(T data, node* Ptr)
{
if (Ptr != NULL)
{
if (Ptr->data == data)
return Ptr;
else if (data < Ptr->data)
ReturnNode(data, Ptr->left);
else
ReturnNode(data, Ptr->right);
}
else
return NULL;
}
T BSTree::ReturnRootData()
{
if (root != NULL)
{
return root->data;
}
else return -1000;
}
void BSTree::PrintChildren(T data)
{
node* Ptr = ReturnNode(data, root);
if (root != NULL)
{
cout << "The parent Node " << Ptr->data << endl;
Ptr->left == NULL ?
cout << "Left Child = NULL" << endl :
cout << "Left Child = " << Ptr->left->data << endl;
Ptr->right == NULL ?
cout << "Right Child = NULL" << endl :
cout << "Right Child = " << Ptr->right->data << endl;
}
else cout << "Data " << data << " is not in the tree." << endl;
}
T BSTree::FindSmallest()
{
return FindSmallestPrivate(root);
}
T BSTree::FindSmallestPrivate(node* Ptr)
{
if (root == NULL)
{
cout << "The tree is empty." << endl;
return -1000;
}
else {
if (Ptr != NULL)
{
if (Ptr->left != NULL)
return FindSmallestPrivate(Ptr->left);
else
return Ptr->data;
}
}
}
void BSTree::RemoveRootMatch()
{
if (root != NULL)
{
node* DelPtr = root;
T rootData = root->data;
T SmallestInRightTree;
if (root->left == NULL && root->right == NULL)
{
root = NULL;
delete DelPtr;
}
if (root->left != NULL && root->right == NULL)
{
root = root->left;
DelPtr->left = NULL;
delete DelPtr;
}
if (root->left == NULL && root->right != NULL)
{
root = root->right;
DelPtr->right = NULL;
delete DelPtr;
}
if (root->left != NULL && root->right != NULL)
{
SmallestInRightTree = FindSmallestPrivate(root->right);
RemoveNodePrivate(SmallestInRightTree, root);
root->data = SmallestInRightTree;
}
}
else
cout << "Can't remove the data. The tree is empty.";
}
void BSTree::RemoveMatch(node* parent, node* match, bool left)
{
if (root)
{
node* DelPtr;
T matchData = match->data;
T SmallestInRightTree;
if (match->left == NULL && match->right == NULL)
{
DelPtr = match;
left == true ? parent->left = NULL : parent->right = NULL;
delete DelPtr;
}
else if (match->left != NULL && match->right == NULL)
{
left == true ? parent->left = match->left : parent->right = match->left;
match->left = NULL;
DelPtr = match;
delete DelPtr;
}
else if (match->left == NULL && match->right != NULL)
{
left == true ? parent->left = match->right : parent->right = match->right;
match->right = NULL;
DelPtr = match;
delete DelPtr;
}
else {
SmallestInRightTree = FindSmallestPrivate(match->right);
RemoveNodePrivate(SmallestInRightTree, match);
match->data = SmallestInRightTree;
}
}
else
cout << "Can't remove the data. The tree is empty.";
}
void BSTree::RemoveNode(T data)
{
RemoveNodePrivate(data, root);
}
void BSTree::RemoveNodePrivate(T data, node* parent)
{
if (root != NULL)
{
if (root->data == data)
RemoveRootMatch();
else
{
if (data < parent->data && parent->left != NULL)
{
parent->left->data == data ?
RemoveMatch(parent, parent->left, true) :
RemoveNodePrivate(data, parent->left);
}
else if (data > parent->data && parent->right != NULL)
{
parent->right->data == data ?
RemoveMatch(parent, parent->right, false) :
RemoveNodePrivate(data, parent->right);
}
else
cout << "The data " << data << " was not found in the tree" << endl;
}
}
else cout << "The tree is empty." << endl;
}
bool BSTree::isFull()
{
isFullPrivate(root);
return varIsFull;
}
void BSTree::isFullPrivate(node* current)
{
if (current == NULL) return;
if (current->left == NULL && current->right != NULL)
varIsFull = false;
else if (current->left != NULL && current->right == NULL)
varIsFull = false;
isFullPrivate(current->left);
isFullPrivate(current->right);
}
void BSTree::RemoveTree(node* Ptr)
{
if (Ptr != NULL)
{
if (Ptr->left != NULL)
RemoveTree(Ptr->left);
if (Ptr->right != NULL)
RemoveTree(Ptr->right);
delete Ptr;
}
}Source.cpp
#include <conio.h>
#include "Tree.h"
int main()
{
int TreeData[] = { 56, 354, 23, 76, 34, 60, 12, 5, 89, 53 };
BSTree MyTree;
for (int i = 0; i < 10; i++)
MyTree.AddLeaf(TreeData[i]);
cout << "Print Preorder: ";
MyTree.PrintPreorder();
cout << "Print Postorder: ";
MyTree.PrintPostorder();
cout << "Print Inorder: ";
MyTree.PrintInOrder();
cout << "The smallest data in tree is: " << MyTree.FindSmallest() << endl;
cout << "Remove node with data 56, 60, 34 from the tree: ";
cout << "\nPrint tree(preorder): ";
MyTree.RemoveNode(56);
MyTree.RemoveNode(60);
MyTree.RemoveNode(34);
MyTree.PrintPreorder();
cout << "The Tree's root data is: " << MyTree.ReturnRootData();
if (MyTree.isFull())
cout << "\nThat is full tree.";
else cout << "\nThat isn't full tree.";
_getch();
return 0;
}
Скріншот виконання
Висновок
На даній лабораторній роботі я набув практичних навичок побудови черги, дослідив динаміку його вмісту та використання для розв'язання прикладних задач.
28.05.2019 18:05-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора