МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА” Кафедра ЕОМ ЗВІТ лабораторної роботи №7 з дисципліни “Структури даних та алгоритми” на тему: “ Структура даних "Бінарне дерево пошуку" ” Варіант № 2 1. МЕТА РОБОТИ Вивчення абстрактної структури даних "Бінарне дерево пошуку". Набуття практичних навичок побудови дерева та використання його для розв'язання прикладних задач. 2. ПОСТАНОВКА ЗАДАЧІ Побудувати бінарне дерево пошуку для послідовності чисел, що вводяться з клавіатури. Виконати обхід дерева у заданому порядку та підрахувати: кількість вершин дерева при проходженні його у прямому порядку; кількість листків дерева при проходженні його у зворотньому порядку; кількість вузлів, що мають тільки одного нащадка при проходженні дерева у симетричному порядку. Виконати індивідуальне завдання згідно з варіантом: 2. Вилучити з дерева всi листки. 3. АЛГОРИТМ РОЗВ’ЯЗАННЯ ЗАДАЧІ Текст інтерфейсу class BTree { int key; //Дані вузла int left; //Номер індекса масиву лівого вузла int right; //Номер індекса масиву правого вузла int father; //Номер індекса масиву вузла - батька int dat[TreeSize];//масив даних int leftTree [TreeSize];//масив лівих адрес int rightTree[TreeSize];//масив правих адрес int fatherTree[TreeSize];//масив батьків public: BTree(); void pop(int);// додає елемент void delete_(int); int getElement(int); void show(); void enterRoot(int); int ob_1(int); int postorderPrint(int); int inorderPrint(int); }; / Рис.1 Виконання першого завдання Для виконання завдання 2 допишемо ще одну функцію. int BTree::del_2(int i) { if (i == -1) // базовий випадок { return 0; } del_2(leftTree[i]); del_2(rightTree[i]); if(leftTree[i] == -1 && rightTree[i] == -1) { dat[i] = NULL; leftTree[i] = -1; rightTree[i] = -1; fatherTree[i] = -1; } } / Рис,2 Виконання завдання 2. Висновки: Я вивчив структуру даних бінарне дерево пошуку. Набув практичних навичок побудови бінарних дерев пошуку, дослідження динаміки вмісту та використання бінарних дерев пошуку для розв'язання прикладних задач. Додаток #include<iostream> #include <string> using namespace std; #define FREE -1 #define Nil -2147483647 #define TreeSize 10 int t; class BTree { int key; //Дані вузла int left; //Номер індекса масиву лівого вузла int right; //Номер індекса масиву правого вузла int father; //Номер індекса масиву вузла - батька int dat[TreeSize];//масив даних int leftTree [TreeSize];//масив лівих адрес int rightTree[TreeSize];//масив правих адрес int fatherTree[TreeSize];//масив батьків public: BTree(); void pop(int);// додає елемент void delete_(int); int getElement(int); void show(); void enterRoot(int); int ob_1(int); int postorderPrint(int); int inorderPrint(int); int del_2(int ); }; BTree::BTree(){ key = NULL; left = FREE; right = FREE; father = FREE; } void BTree::enterRoot(int key_) { for(int i = 0; i < TreeSize;i++) { dat[i] = NULL; } for(int i = 0; i < TreeSize;i++) { leftTree[i] = FREE; } for(int i = 0; i < TreeSize;i++) { rightTree[i] = FREE; } for(int i = 0; i < TreeSize;i++) { fatherTree[i] = FREE; } dat[0] = key_; //rightTree[0] } void BTree::pop(int key_) { for(int i = 0;i < TreeSize; i++) { if(dat[i] == NULL) { t=0; int v=0; dat[i] = key_; while (t != -1) { if(dat[t] > key_) { v = t; t = leftTree[t]; } else { v =t; t = rightTree[t]; } } if(dat[v] > key_) { leftTree[v] = i; } else { rightTree[v] = i; } fatherTree[i]= v; break; } } } void BTree::show() { for(int i = 0; i < TreeSize; i++) { cout<<i<<" \t"; } cout<<endl; for(int i = 0; i < TreeSize; i++) { cout<<dat[i]<<" \t"; } cout<<endl; for(int i = 0; i < TreeSize; i++) { cout<<leftTree[i]<<" \t"; } cout<<endl; for(int i = 0; i < TreeSize; i++) { cout<<rightTree[i]<<" \t"; } cout<<endl; for(int i = 0; i < TreeSize; i++) { cout<<fatherTree[i]<<" \t"; } } void BTree::delete_(int key_) { int x =0; for(int i = 0; i < TreeSize; i++) { if(dat[i] == key_) { if(leftTree[i] == -1 && rightTree[i] == -1 )//перевіряємо чи вершина є листком { x = fatherTree[i]; if(dat[x] > key_) { leftTree[x] = -1; } else { rightTree[x] = -1; } dat[i] = NULL; leftTree[i] = -1; rightTree[i] = -1; fatherTree[i] = -1; break; } //*********************************************************************************************** if(leftTree[i] != -1 && rightTree[i] != -1 )//перевіряємо чи вершина два піддерева { t=i; int v = 0; while(t != -1) { v = t; t = rightTree[t]; } dat[i] = dat[v]; dat[v] = NULL; leftTree[v] = -1; rightTree[v] = -1; fatherTree[v] = -1; break; } //*********************************************************************************************** if(leftTree[i] == -1 || rightTree[i] == -1 )//Перевіряємо чи вершина має піддерва { if(rightTree[i] != -1) { //підключаємо праве піддерево dat[i] = NULL; rightTree[fatherTree[i]] = rightTree[i]; fatherTree[rightTree[i]] = fatherTree[i]; leftTree[i] = -1; rightTree[i] = -1; fatherTree[i] = -1; break; } else//підключаємо ліве піддерево { dat[i] = NULL; leftTree[fatherTree[i]] = leftTree[i]; fatherTree[leftTree[i]] = fatherTree[i]; leftTree[i] = -1; rightTree[i] = -1; fatherTree[i] = -1; break; } } } } } int BTree::ob_1(int i) { if( i == -1) { return 0; } cout << dat[i]<<" "; ob_1(leftTree[i]); ob_1(rightTree[i]); } int BTree::postorderPrint(int i) { if (i == -1) // базовий випадок { return 0; } postorderPrint(leftTree[i]); postorderPrint(rightTree[i]); if(leftTree[i] == -1 && rightTree[i] == -1) cout << dat[i] << " "; } int BTree::inorderPrint(int i) { if (i == -1) // базовий випадок { return 0; } inorderPrint(leftTree[i]); if((leftTree[i] == -1 && rightTree[i] != -1)||(leftTree[i] != -1 && rightTree[i]==-1)) cout << dat[i] << " "; inorderPrint(rightTree[i]); } int BTree::del_2(int i) { if (i == -1) // базовий випадок { return 0; } del_2(leftTree[i]); del_2(rightTree[i]); if(leftTree[i] == -1 && rightTree[i] == -1) { dat[i] = NULL; leftTree[i] = -1; rightTree[i] = -1; fatherTree[i] = -1; } } int main() { BTree obj; int root, v, i=1; string choice; cout << "Maximum number of BT elements 10, \nenter the root - "; cin >> root; obj.enterRoot(root); while (i < TreeSize) { cout << "\nenter the tree element "; cin >> v; obj.pop(v); i++; } obj.show(); cout << "\ndirect bypass of the tree - "; obj.ob_1(0); cout << "\nreverse bypass tree - "; obj.postorderPrint(0); cout << "\nsymmetrical bypass tree - "; obj.inorderPrint(0); cout << "specify the item you want to delete - "; cin >> v; obj.delete_(v); obj.show(); cout << "\ndirect bypass of the tree - "; obj.ob_1(0); cout << "\nreverse bypass tree - "; obj.postorderPrint(0) cout << "\nsymmetrical bypass tree - "; obj.inorderPrint(0); obj.del_2(0); cout << " \n---------------------------------N2--------------------------\n"; obj.show(); return 0; }