Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Поняття бінарного дерева. Обхід бінарного дерева. Створення, відображення дерева. Вставлення, видалення елементів у бінарному дереві
Інформація про навчальний заклад
ВУЗ:
Національний технічний університет України Київський політехнічний інститут
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2024
Тип роботи:
Звіт до лабораторної роботи
Предмет:
Програмування
Частина тексту файла (без зображень, графіків і формул):
НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ
“КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ
імені ІГОРЯ СІКОРСЬКОГО”
ЗВІТ
з лабораторної роботи №7
з навчальної дисципліни “Програмування складних алгоритмів”
Тема: «Поняття бінарного дерева.
Обхід бінарного дерева. Створення, відображення дерева.
Вставлення, видалення елементів у бінарному дереві»
Варіант № 15
Дата « 19» червня 2022
Мета роботи: набути навичок створення та обробки бінарних дерев.
Теоретичні відомості:
Дерево – це структура даних, що являє собою сукупність елементів і відносин, що утворюють ієрархічну структуру цих елементів.
Кожен елемент дерева називається вершиною (вузлом) дерева. Вершини дерева з’єднані спрямованими дугами, які називають гілками дерева.
Початковий вузол дерева називають коренем дерева, йому відповідає нульовий рівень. Листями дерева називають вершини, в які входить одна гілка і не виходить жодної гілки.
Кожне дерево має такі властивості:
1) існує вузол, в який не входить ні одна дуга (корінь);
2) у кожну вершину, крім кореня, входить одна дуга.
Дерева особливо часто використовують на практиці при зображенні різних ієрархій.
/
Бінарні дерева є деревами зі ступенем не більше двох.
Бінарне (двійкове) дерево − це динамічна структура даних, що являє собою дерево, в якому кожна вершина має не більше двох нащадків.
Таким чином, бінарне дерево складається з елементів, кожен з яких містить інформаційне поле і не більше двох посилань на різні бінарні піддерева. На кожен елемент дерева є рівно одне посилання.
/
Кожна вершина бінарного дерева є структурою, що складається з чотирьох видів полів. Вмістом цих полів будуть відповідно:
інформаційне поле (ключ вершини);
службове поле (їх може бути декілька або жодного);
покажчик на ліве піддерево;
покажчик на праве піддерево;
Процес доступу до елементів дерева називається проходженням дерева.
Існує три способи проходження дерев: послідовний, низхідний та висхідний.
При послідовному методі: спочатку розглядається самий лівий відносно кореня елемент, потім його батьківський вузол, потім правий елемент даної ланки, потім переходять до елемента попереднього рівня, що є батьківським по відношенню до батьківського вузла даної ланки і т. д.Вверх до кореня, а потім від кореня вниз до самого правого елемента.
Операції з деревами При низхідному проходженні дерева порядок обходу елементів зверху-вниз та зліва-направо. Тобто спочатку проходиться корінь, потім його лівий елемент, а потім правий і т.д.
При висхідному проходженні порядок проходження зліва-направо та знизу-вверх. Тобто спочатку проходиться лівий вузол найнижчої ланки, потім правий вузол цієї ланки, а потім їх батьківський вузол і т.д. /
Завдання для виконання:
/
Результат виконання:
/
/
Висновок: під час виконання даної лабораторної роботи було набуто практичних навичок щодо створення та обробки бінарних дерев. Було виконано завдання відповідно варіанту. Програма працює відповідно вимог, усе працює справно.
Посилання на Replit: https://replit.com/join/byayghwlko-tr-15fundamient
Код програми:
#include <iostream>
using namespace std;
class Tree {
int data;
Tree* left;
Tree* right;
public:
Tree();
Tree(int tdata);
void treePrint(Tree* tree, int level);
void treeFilling(int data);
void replaceZeros(Tree* tree);
void sonsSum(Tree* tree, int counter);
};
Tree::Tree(){
left = NULL;
right = NULL;
};
Tree::Tree(int tdata) {
data = tdata;
left = NULL;
right = NULL;
}
void Tree::treePrint(Tree* tree, int level=0)
{
if (tree)
{
treePrint(tree->left, level + 1);
for (int i = 0; i < level; i++) cout << " ";
cout << tree->data << endl;
treePrint(tree->right, level + 1);
}
}
void Tree::treeFilling(int data) {
Tree* temp = this;
while(true) {
if(data < temp->data) {
if (temp->left == NULL)
{
temp->left = new Tree;
temp->left->data = data;
break;
}
else temp = temp->left;
} else if(data >= temp->data) {
if (temp->right == NULL)
{
temp->right = new Tree;
temp->right->data = data;
break;
}
else temp = temp->right;
}
}
}
void Tree::replaceZeros(Tree* tree) {
if(tree->left != NULL) {
replaceZeros(tree->left);
}
if(tree->right != NULL) {
replaceZeros(tree->right);
}
if(tree->data < 0) {
tree->data = 0;
}
}
void Tree::sonsSum(Tree *tree, int counter = 0) {
int sum = 0;
if(tree->left != NULL && tree->right != NULL) {
sum = tree->left->data + tree->right->data;
if(sum % 2 == 0) {
cout << "Sum on counter (" << counter << ") is equal: " << sum << endl;
}
counter++;
sonsSum(tree->left, counter);
sonsSum(tree->right, counter);
} else if(tree->left == NULL && tree->right != NULL) {
sum = tree->right->data;
if(sum % 2 == 0) {
cout << "Sum on counter (" << counter << ") is equal: " << sum << endl;
}
counter++;
sonsSum(tree->right, counter);
} else if(tree->left != NULL && tree->right == NULL) {
sum = tree->left->data;
if(sum % 2 == 0) {
cout << "Sum on counter (" << counter << ") is equal: " << sum << endl;
}
counter++;
sonsSum(tree->left, counter);
}
}
int main() {
Tree* tree = new Tree(7);
int temp;
int treeCapacity;
cout << "Enter number of tree elements: \n";
cin >> treeCapacity;
for(int i = 0; i < treeCapacity; i++) {
cout << "Enter " << i << " tree element:\n";
cin >> temp;
tree->treeFilling(temp);
}
cout << "\nInitial tree:\n";
tree->treePrint(tree);
cout << "\n---- Tree after replacement: ----\n";
tree->replaceZeros(tree);
tree->treePrint(tree);
cout << "\n---- Sum of each element sons: ----\n";
tree->sonsSum(tree);
}
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора