Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Поняття бінарного дерева. Обхід бінарного дерева. Створення, відображення дерева. Вставлення, видалення елементів у бінарному дереві.
Інформація про навчальний заклад
ВУЗ:
Національний технічний університет України Київський політехнічний інститут
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2022
Тип роботи:
Звіт до лабораторної роботи
Предмет:
Програмування складних алгоритмів
Частина тексту файла (без зображень, графіків і формул):
НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ
“КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ
імені ІГОРЯ СІКОРСЬКОГО”
ЗВІТ
з лабораторної роботи №7
з навчальної дисципліни “Програмування складних алгоритмів”
Тема: «Поняття бінарного дерева. Обхід бінарного дерева. Створення, відображення дерева. Вставлення, видалення елементів у бінарному дереві.»
Варіант № 16
Дата « 20 » червня 2022
Мета роботи: набути навичок створення та обробки бінарних дерев.
Завдання до лабораторної роботи: Розробити спосіб створення бінарного дерева та його зберігання. Виконати індивідуальне завдання над бінарним деревом. Вивести елементи дерева до та після обробки.
/
Теоретичні відомості:
The tree is a hierarchical Data Structure. A binary tree is a tree that has at most two children. The node which is on the left of the Binary Tree is called “Left-Child” and the node which is the right is called “Right-Child”. Also, the smaller tree or the subtree in the left of the root node is called the “Left sub-tree” and that is on the right is called “Right sub-tree”.
/
Source: https://www.geeksforgeeks.org/tutorial-on-binary-tree/?ref=lbp
Шлях по якому програма обходить дерево:
/
Результат роботи програми:
/
/
/
Посилання на код:
https://replit.com/join/nvmbkzzltf-tr-15khavkin
#include "bits/stdc++.h"
using namespace std;
// Structure of the Binary Tree
struct treenode {
int info;
struct treenode *left, *right;
};
// Function to create the Binary Tree
struct treenode* create(){
int data;
struct treenode* tree;
// Dynamically allocating memory
// for the tree-node
tree = new treenode;
cout << "\nEnter data to be inserted " << "or type -1 for no insertion : ";
// Input from the user
cin >> data;
// Termination Condition
if (data == -1)
return 0;
// Assign value from user into tree
tree->info = data;
// Recursively Call to create the
// left and the right sub tree
cout << "Enter left child of : " << data;
tree->left = create();
cout << "Enter right child of : " << data;
tree->right = create();
// Return the created Tree
return tree;
};
int Rev(int n){
int reverse = 0, rem;
while (n > 0) {
rem = n % 10;
reverse = reverse * 10 + rem;
n /= 10;
}
return reverse;
}
void invertel(struct treenode* root){
// If the root is NULL
if (root == NULL)
return;
// Using tree-node type stack STL
stack<treenode*> s;
while ((root != NULL) || (!s.empty())) {
if (root != NULL) {
// Reverse the root
root->info=Rev(root->info);
// Push the node in the stack
s.push(root);
// Move to left subtree
root = root->left;
}else {
// Remove the top of stack
root = s.top();
s.pop();
root = root->right;
}
}
}
void LeftRight(struct treenode* root){
int h=0,k1=0,k2=0,l=0,r=0,head;
stack<treenode*> s;
head=root->info;
while ((root != NULL) || (!s.empty())) {
if (root != NULL) {
if(h<2 && l==0 && root->info!=head){
cout<< "Left subtree even: ";
l++;
}
if(h>2 && r==0 && root->info!=head){
cout<< endl << "Right subtree even: ";
r++;
}
if(((root->info)%2!=1) && h<1 && root->info!=head){
k1++;
cout << root->info << " ";
}else if(((root->info)%2!=1) && h>1 && root->info!=head){
k2++;
cout << root->info << " ";
}
s.push(root);
root = root->left;
}else {
root = s.top();
s.pop();
root = root->right;
h++;
}
}
cout << endl;
if(k1>k2){
cout << "Left subtree have more even";
}else if(k1<k2){
cout << "Right subtree have more even";
}else {
cout << "Same amount of even";
}
}
// Function to perform the pre-order
// traversal for the given tree
void preorder(struct treenode* root){
// If the root is NULL
if (root == NULL)
return;
// Using tree-node type stack STL
stack<treenode*> s;
cout << "Walk: ";
while ((root != NULL) || (!s.empty())) {
if (root != NULL) {
// Print the root
cout << root->info << " ";
// Push the node in the stack
s.push(root);
// Move to left subtree
root = root->left;
}else {
// Remove the top of stack
root = s.top();
s.pop();
root = root->right;
}
}
cout << endl;
}
int main(){
// Root Node
struct treenode* root = NULL;
cout << "Please enter 9 elements like that:" << endl << " __ a __" << endl << " | |" << endl << " a1 a2" << endl << " / | / | " << endl << " a1.1 a1.2 a2.1 a2.2" << endl;
// Function Call
root = create();
// Perform Inorder Traversal
preorder(root);
invertel(root);
preorder(root);
LeftRight(root);
return 0;
}
/* Will be creating tree:
__ a __
/ \
a1 a2
/ \ / \
a1.1 a1.2 a2.1 a2.2
*/
Висновок: У цій лабораторної роботі ознайомилися з принципами існування, створення та збереження бінарних дерев. Було розроблено структуру для зберігання дерева та функції що створюють та обробляють дерево. Виконали завдання згідно до індивідуального варіанту. Зроблено звіт до лабораторної роботи та надіслано викладачу.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора