Міністерство освіти і науки України Національний університет „Львівська політехніка” Звіт з лабораторної роботи № 7 з дисципліни: “Структури даних та алгоритми» На тему: “ Структура даних БІНАРНЕ ДЕРЕВО ПОШУКУ” Варіант 9 1. МЕТА РОБОТИ Вивчення абстрактної структури даних "Бінарне дерево пошуку". Набуття практичних навичок побудови дерева та використання його для розв'язання прикладних задач. 2. ЗАВДАННЯ 2.1 Постановка задачі 2.1.1 Побудувати бінарне дерево пошуку для послідовності чисел, що вводяться з клавіатури. Реалізувати операції додавання та вилучення вузлів з бінарного дерева пошуку. Виконати обхід дерева у заданому порядку та показати: 1. послідовність вершин дерева при проходженні його у прямому порядку; 2. послідовність листків дерева при проходженні його у зворотньому порядку; 3. послідовність вузлів, що мають тільки одного нащадка при проходженні дерева у симетричному порядку. 2.1.2 Знайти середнє арифметичне значення всіх листків дерева.. 2.2 Алгоритм розв’язання задачі 2.2.1 Створюю новий проект C++ в середовищі розробки Visual Studio 2017 2.2.2 Моделюю бінарне дерево пошуку згідно з завданням, переписуючи основні операції роботи з деревом: void add_node(int x, TreeNode *&MyTree) //Додавання нового вузла(вершини) void ShowSort(TreeNode *&Tree) //Відображення бінарного дерева у відсортированому порядку TreeNode* deleteElem(TreeNode* root, int elem) /Видалення вузла void levelOrderPrint(TreeNode *root) //Відображення по рівням void del(TreeNode *&Tree) //Видалення динамічної пам'яті void preorderPrint(TreeNode *root) //Відображення бінарного дерева у прямому порядку void postorderPrint(TreeNode *root) //Відображення бінарного дерева у зворотньому порядку void inorderPrint(TreeNode *root) //Відображення бінарного дерева у рекурсивному порядку 2.2.3 Виконую індивідуальне завдання згідно з варіантом; 2.2.4 Закінчую створення програми та перевіряю правильність її виконання. 2.3 Результати виконання програми / Рис 2.3 Результат виконання програми ВИСНОВКИ Під час виконання лабораторної роботи я набув практичних навичок побудови черги, дослідив динаміку його вмісту та використання черг для розв'язання прикладних задач. ДОДАТКИ Файл Tree.h #pragma once #include "stdafx.h" #include <queue> #include<iostream> #include <stack> int COUNT = 0; using namespace std; struct TreeNode { int data; // ключ TreeNode *left; // вказівник на лівого потомка TreeNode *right; // вказівник на правого потомка }; //Додавання нового вузла(вершини) void add_node(int x, TreeNode *&MyTree) { if (NULL == MyTree) { MyTree = new TreeNode; //Виділення пам'яті MyTree->data = x; //Запис даних MyTree->left = MyTree->right = NULL; //Ініціалізація підвершин пустотой } if (x<MyTree->data) //Якщо новий елемент менше вершини - ідем вліво { if (MyTree->left != NULL) add_node(x, MyTree->left); //Рекурсією штовхаєм елемент else //Якщо знайшли участок елементу { MyTree->left = new TreeNode; //Виділяєм пам'ять MyTree->left->left = MyTree->left->right = NULL; //Ініціалізуєм його лівий та правий вузол MyTree->left->data = x; //Записуєм елемент в наш знайдений участок } } if (x>MyTree->data) //Якщо елемент більший вершини - ідем вправо { if (MyTree->right != NULL) add_node(x, MyTree->right); else { MyTree->right = new TreeNode; MyTree->right->left = MyTree->right->right = NULL; MyTree->right->data = x; } } } //Відображення бінарного дерева у відсортированому порядку void ShowSort(TreeNode *&Tree) { if (Tree != NULL) { ShowSort(Tree->left); //Рекурсивна функція для вивода лівого піддерева cout << Tree->data<<" "; //Відображення кореня ShowSort(Tree->right); //Рекурсивна функція для вивода правого піддерева } } TreeNode* findPred(TreeNode* root) { static TreeNode* pred; if (root == NULL) { return pred; } else { pred = root; return findPred(root->right); } } //Видалення вузла TreeNode* deleteElem(TreeNode* root, int elem) { TreeNode* save; if (root == NULL) { printf("Element not in the tree !\n"); return NULL; } if (root->data == elem) { if (root->right == NULL && root->left == NULL) { free(root); return NULL; } else if (root->right == NULL || root->left == NULL) { if (root->right == NULL) { save = root->left; free(root); return save; } else { save = root->right; free(root); return save; } } else { save = findPred(root->left); root->data = save->data; root->left = deleteElem(root->left, root->data); return root; } } else if (root->data < elem) { root->right = deleteElem(root->right, elem); } else if (root->data > elem) { root->left = deleteElem(root->left, elem); } return root; } //Відображення по рівням void levelOrderPrint(TreeNode *root) { if (root == NULL) { return; } queue<TreeNode *> q; //Створюємо чергу q.push(root); // Вставляєм елемент в чергу while (!q.empty()) { TreeNode* temp = q.front(); //Берем перший елемент черги q.pop(); // Видаляєм перший елемент черги cout << temp->data << " "; // Друкуєм перший елемент черги if (temp->left != NULL) q.push(temp->left); // Вставляєм в чергу лівого потомка if (temp->right != NULL) q.push(temp->right); // Вставляєм в чергу правого потомка } } //Видаляєм динамічну пам'ять void del(TreeNode *&Tree) { if (Tree != NULL) { del(Tree->left); del(Tree->right); delete Tree; Tree = NULL; } } //Відображення бінарного дерева у прямому порядку void preorderPrint(TreeNode *root) { if (root == NULL) { return; } cout << root->data << " "; preorderPrint(root->left); //рекурсивний виклик лівого піддерева preorderPrint(root->right); //рекурсивний виклик правого піддерева } //Відображення бінарного дерева у зворотньому порядку void postorderPrint(TreeNode *root) { if (root == NULL) { return; } preorderPrint(root->left); preorderPrint(root->right); cout << root->data << " "; } //Відображення бінарного дерева у рекурсивному порядку void inorderPrint(TreeNode *root) { if (root == NULL) { return; } preorderPrint(root->left); cout << root->data << " "; preorderPrint(root->right); } //Відображення листків дерева при проходженні у прямому порядку void preorderPrintEX(TreeNode *root) { if (root == NULL) { return; } if ((root->left) == NULL && (root->right) == NULL)//Перевірка на лівого та правого нащадка { cout << root->data; } cout << " "; preorderPrintEX(root->left); preorderPrintEX(root->right); } //Відображення листків дерева при проходженні в зворотньому порядку void postorderPrintEX(TreeNode *root) { if (root == NULL) { return; } preorderPrintEX(root->left); preorderPrintEX(root->right); } //Відображення вузлів що мають лише одного нащадка при проходженні у прямому порядку void preorderPrintEX2(TreeNode *root) { if (root == NULL) { return; } //Перевірка на наявність лише лівого або лише правого нащадка if ((root->left) == NULL && (root->right) != NULL|| (root->left) != NULL && (root->right) == NULL) { cout << root->data; } cout << " "; preorderPrintEX2(root->left); preorderPrintEX2(root->right); } //Відображення вузлів що мають лише одного нащадка при проходженні у симетричному порядку void inorderPrintEX(TreeNode *root) { if (root == NULL) { return; } preorderPrintEX2(root->left); preorderPrintEX2(root->right); } //Сума всіх елементів дерева int Amount(TreeNode *root) { if (root == NULL) { return 0; } return ((root->data) + Amount(root->left) + Amount(root->right));//Рекурсивний виклик функції для лівого та правого піддерева } //Середнє арифметичне всіх елементів дерева double Average(TreeNode *root, int n) { return (double)Amount(root) / n; } //Сума лістків дерева double AmountLeaves(TreeNode *root) { if (root == NULL) { return 0; } if ((root->left) == NULL && (root->right) == NULL) { COUNT++;//Лічильник кількості листків return (root->data); } return (AmountLeaves(root->left) + AmountLeaves(root->right)); } //Середнє арифметичне листків double AverageLeaves(TreeNode *root) { return AmountLeaves(root) / COUNT; } Файл lab7.cpp #include "stdafx.h" #include"Tree.h" #include <array> int main() { TreeNode *Tree = NULL; //Послідовність з клавіатури cout << "Enter the size:"; int size; cin >> size; for (int i = 0; i < size; i++) { static int tmp; cout << "New element:"; cin >> tmp; add_node(tmp, Tree); } //Послідовність з масиву /*array<int, 13> arr = { 12, 7, 5 ,9, 10,3,6,14,17,8,13, 2 , 21 }; for (auto i:arr) add_node(i, Tree);*/ cout << endl; cout << "Vertices in the preorder:"; preorderPrint(Tree); cout << endl; cout << "Vertices in the postorder:"; postorderPrint(Tree); cout << endl; cout << "Leaves in the postorder:"; postorderPrintEX(Tree); cout << endl; cout << "Vertices in the symmetric:"; inorderPrint(Tree); cout << endl; cout << "Nodes with one descendant in the symmetric:"; inorderPrintEX(Tree); cout << endl; cout << "Average leaves:"; cout << AverageLeaves(Tree)<<endl; cout << endl; del(Tree); return 0; }