Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Поняття бінарного дерева. Обхід бінарного дерева. Створення, відображення дерева. Вставлення, видалення елементів у бінарному дереві
Інформація про навчальний заклад
ВУЗ:
Національний технічний університет України Київський політехнічний інститут
Інститут:
Не вказано
Факультет:
ЗІ
Кафедра:
Не вказано
Інформація про роботу
Рік:
2022
Тип роботи:
Звіт до лабораторної роботи
Предмет:
Програмування складних алгоритмів
Частина тексту файла (без зображень, графіків і формул):
Національний технічний університет України
«Київський політехнічний інститут імені Ігоря Сікорського»
ЗВІТ
до лабораторної роботи № 7
з дисципліни «Програмування складних алгоритмів»
Тема «Поняття бінарного дерева. Обхід бінарного дерева. Створення, відображення дерева. Вставлення, видалення елементів у бінарному дереві»
Варіант № 11
Лабораторна робота № 7
Поняття бінарного дерева. Обхід бінарного дерева. Створення, відображення дерева. Вставлення, видалення елементів у бінарному дереві
Мета: набути навичок створення та обробки бінарних дерев.
Завдання до лабораторної роботи
Сформулювати математичну постановку задачі. Обрати метод розв’язання задачі, якщо це необхідно. Розробити графічну схему алгоритму. Записати розроблений алгоритм мовою програмування за варіантом у списку. Представити звіт до роботи.
Варіант
Обхід дерева
Завдання
11
Послідовний
1. Обчислити середнє арифметичне елементів дерева.
2. Вивести на екран ті листи дерева, які мають непарні значення.
Теоретичні відомості
Дерева пошуку являють собою структури даних, що підтримують операції пошуку елемента, мінімального і максимального значення, попередника й наступника, вставку і видалення.
Основні операції в бінарному дереві пошуку виконуються за час, пропорційний його висоті. Для повного бінарного дерева з n вузлами ці операції виконуються за час O(lg n) у найгіршому випадку. Математичне сподівання висоти побудованого випадковим чином бінарного дерева рівне O(lg n), так що всі основні операції над динамічною множиною в такім дереві виконуються в середньому за час O(lg n).
На практиці не завжди можна гарантувати випадковість побудови бінарного дерева пошуку, однак існують версії дерев, у яких гарантується гарний час роботи в найгіршому випадку, а саме — червоно-чорні дерева, висота яких O(lg n).
Структура бінарного дерева
Бінарне дерево може бути представлене за допомогою зв'язаної структури даних, у якій кожен вузол є об'єктом. На додаток до полів ключа key і супутніх даних, кожен вузол містить поля left, right і p, що вказують на лівий і правий дочірні вузли і на батьківський вузол відповідно. Якщо дочірній чи батьківський вузол відсутні, відповідне поле містить значення NULL. Єдиний вузол, вказівник p якого дорівнює NULL, — це кореневий вузол дерева. Ключі в бінарному дереві пошуку зберігаються таким чином, щоб у будь-який момент задовольняти наступній властивості бінарного дерева пошуку:
Якщо x — вузол бінарного дерева пошуку, а вузол y знаходиться в лівому піддереві вузла x, то key [y] ≤ key [x]. Якщо вузол y знаходиться в правому піддереві вузла x, то key [x] ≤ key [y].
/
Рисунок 1. Приклад бінарного дерева
Властивість бінарного дерева пошуку дозволяє нам вивести всі ключі, що знаходяться в дереві, у відсортованому порядку за допомогою простого рекурсивного алгоритму, названого симетричним обходом дерева (inorder tree walk). Цей алгоритм одержав дану назву в зв'язку з тим, що ключ у корені піддерева виводиться між значеннями ключів лівого і правого піддерева. Існують й інші способи обходу, а саме — обхід у прямому порядку (preorder tree walk), при якому спочатку виводиться корінь, а потом — значення лівого і правого піддерева, і обхід у зворотному порядку (postorder tree walk), коли першими виводяться значення лівого і правого піддерева, а уже потім — кореня.
Для обходу дерева потрібен час О(n), оскільки після початкового виклику процедура викликається рівно два рази для кожного вузла дерева: один раз для його лівого дочірнього вузла, і один раз — для правого.
Операції вставки і видалення приводять до внесення змін у динамічну множину, що представлена бінарним деревом пошуку. Структура даних повинна бути змінена таким чином, щоб відбивати ці зміни, але при цьому зберегти властивості бінарних дерев пошуку.
Результати роботи
Створюємо структуру BinTree з полями: дані, ліве та праве піддерево.
Функція newBinTree() відповідає за створення дерева. Перевіряємо умову: якщо дерева не існує, то виділяємо пам’ять під корінь (потім під листок) і записуємо туди значення. Тобто, на цьому етапі ми створили корінь дерева. Всі інші елементи записуватимуться у ліве та праве піддерева. Якщо значення менше за корінь, записуємо його у ліве піддерево. У іншому випадку записуємо у праве.
Функція Print() виводить на екран дерево. Перевіряємо умову: якщо елементів немає, повертаємось. В іншому випадку працюватимемо з елементами. Для цього створюємо чергу і функцією .push() додаємо до неї елемент із дерева. Поки черга не пуста, у змінну node записуємо перший елемент із черги, виводимо його на екран, а із черги видаляємо. Записуємо елементи за допомогою послідовного обходу у ліве та праве піддерева. Тобто, елементи записуються рівнево: перший рівень – корінь, другий – його сини, третій – сини лівого та правого піддерева і так далі.
Функція OutputOfOddValues() виводить на екран листи дерева, які мають непарні значення. Перевіряємо умову: якщо елементів немає, повертаємось. В іншому випадку працюватимемо з елементами. Для цього створюємо чергу і функцією .push() додаємо до неї елемент із дерева. Поки черга не пуста, у змінну node записуємо перший елемент із черги. Перевіряємо умову: якщо залишок від ділення на 2 не дорівнює 0, виводимо цей елемент.
Функція DestroyTree() видаляє дерево для звільнення пам’яті. Якщо дерево не пусте, видаляємо ліве піддерево, видаляємо праве піддерево та самий корінь.
У головній функції main() уводимо кількість елементів дерева. Циклом for() задаємо значення з клавіатури, щоразу виділяючи пам’ять для нового листка, та зразу рахуємо суму елементів. Функцією Print() виводимо дерево на екран. Для обчислення середнього арифметичного ділимо суму на кількість елементів. Функцією OutputOfOddValues() виводимо непарні елементи.
1.4. Висновок
У ході лабораторної роботи було ознайомлено з поняттям «бінарне дерево», способами обходу: низхідний, висхідний та послідовний. Написано програмний код, який виділяє пам’ять під елементи дерева, виводить його, рахує середнє арифметичне та виводить непарні елементи.
Лістинг програми
#include <iostream>
#include <queue>
using namespace std;
struct BinTree
{
int data;
BinTree* left;
BinTree* right;
};
//Функція для створення дерева
void newBinTree(int val, BinTree** Tree)
{
if ((*Tree) == NULL)
{
(*Tree) = new BinTree;
(*Tree)->data = val;
(*Tree)->left = (*Tree)->right = NULL;
return;
}
if (val < (*Tree)->data)
newBinTree(val, &(*Tree)->left);
else newBinTree(val, &(*Tree)->right);
}
//Функція виведення дерева при послідовному обході
void Print(BinTree* root)
{
if (root == NULL)
return;
queue<BinTree*> q;
q.push(root);
while (q.empty() == false)
{
BinTree* node = q.front();
cout << node->data << " ";
q.pop();
if (node->left != NULL)
q.push(node->left);
if (node->right != NULL)
q.push(node->right);
}
}
//Функція виведення непарних значень листів дерева
void OutputOfOddValues(BinTree* root)
{
if (root == NULL)
return;
queue<BinTree*> q;
q.push(root);
while (q.empty() == false)
{
BinTree* node = q.front();
if (node->data % 2 != 0)
{
cout << node->data << " ";
}
q.pop();
if (node->left != NULL)
q.push(node->left);
if (node->right != NULL)
q.push(node->right);
}
}
//Видаляємо дерево для звільнення пам'яті
void DestroyTree(BinTree* Tree)
{
if (Tree != NULL)
{
DestroyTree(Tree->left);
DestroyTree(Tree->right);
delete(Tree);
}
}
int main()
{
BinTree* Tree = NULL;
int val, n;
int sum = 0;
cout << "Enter the number of elements: ";
cin >> n;
cout << endl;
for (int i = 0; i < n; i++)
{
cout << "Enter the value of the tree: ";
cin >> val;
sum += val;
newBinTree(val, &Tree);
}
cout << "\nBinary tree:\n";
Print(Tree);
cout << "\n\nThe arithmetic mean of the elements of the tree: " << float(sum) / n << endl;
cout << "\nTree leaves with odd values: ";
OutputOfOddValues(Tree);
DestroyTree(Tree);
return 0;
}
Результати
/
Графічно дерево матиме такий вигляд:
/
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора