НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ “КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ імені ІГОРЯ СІКОРСЬКОГО” ЗВІТ з лабораторної роботи №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-15[ім’я автора приховано] #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 */ Висновок: У цій лабораторної роботі ознайомилися з принципами існування, створення та збереження бінарних дерев. Було розроблено структуру для зберігання дерева та функції що створюють та обробляють дерево. Виконали завдання згідно до індивідуального варіанту. Зроблено звіт до лабораторної роботи та надіслано викладачу.