МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
Кафедра ЕОМ лабораторна робота № 4 Структура даних БІНАРНЕ ДЕРЕВО ПОШУКУ № варіанта = [( 09 ) + (ASCII–код 71 )] % 20 + 1 Варіант 1 Львів-2011 1. Мета роботи: Вивчення абстрактної структури даних "Бінарне дерево пошуку". Набуття практичних навичок побудови дерева та використання його для розв'язання прикладних задач. 2. ПОСТАНОВКА ЗАДАЧІ Побудувати бінарне дерево пошуку для послідовності чисел, що вводяться з клавіатури. Реалізувати операції додавання та вилучення вузлів з бінарного дерева пошуку. Виконати обхід дерева у заданому порядку та показати: послідовність вершин дерева при проходженні його у прямому порядку; послідовність листків дерева при проходженні його у зворотньому порядку; послідовність вузлів, що мають тільки одного нащадка при проходженні дерева у симетричному порядку. Завдання №1 Cтворити дзеркальне до заданого дерево 3. Алгоритм виконання: - зчитування чисел; - добавляння цих чисел на відповідну позицію; - обхід дерева у прямому порядку; - обхід дерева у зворотному порядку; - обхід дерева у симетричному порядку; - створення дерева, дзеркального до заданого; - виведення результатів. 4. Динаміка змін бінарного дерева:





5. Реалізація на базі масиву: Індекси 0 1 2 3 4 5 6 7 8 9 10  Data 0 9 7 14 4 8 9 15 2 6 12  Father 0 2 0 10 2 1 1 3 4 4 0  Left son 0 5 4 0 8 0 0 0 0 0 0  Right son 0 6 1 7 9 0 0 0 0 0 3   6. Проходження бінарного дерева: - пряме:
7 → 4 → 2→ 6 → 9 → 8 → 9 - симетричне:
2 → 4 → 6 → 7 → 8 → 9 → 9 - зворотне:
2 → 6 → 4 → 8 → 9 → 9 → 7 7. Результат виконання:
Висновок: на цій лабораторній роботі я вивчив абстрактну структуру даних "Бінарне дерево пошуку". Набув практичних навичок побудови дерева та використання його для розв'язання прикладних задач. Додаток #include <iostream> #include <ctime> #include <cstdlib> #include "node.h" class tree { public: tree(); ~tree(); node* head; node* curr; void generate_random_tree(int size); void symetric_direction(node* curr); void reverse_direction(node* curr); void direct_direction(node* curr); tree mirror(node* curr); }; tree::tree() { head = new node(); curr = head; } tree::~tree() { delete [] head; } void tree::generate_random_tree(int size) { int choise; curr->set_random_data(); size--; while (size != 0) { choise = rand() % 2; if (choise == 0) { curr->add_left_son(); curr = curr->left_son; curr->set_random_data(); } else { curr->add_right_son(); curr = curr->right_son; curr->set_random_data(); } size--; } } void tree::symetric_direction(node* curr) { if (curr->left_son != NULL) { symetric_direction(curr->left_son); std::cout << curr->data << " "; if (curr->right_son != NULL) symetric_direction(curr->right_son); } else { std::cout << curr->data << " "; if (curr->right_son != NULL) { symetric_direction(curr->right_son); } } } tree tree::mirror(node* curr) { tree y; if (curr->left_son != NULL) { y.head->add_left_son(curr->left_son->data); mirror(curr->left_son); if (curr->right_son != NULL) { y.head->add_left_son(curr->left_son->data); mirror(curr->right_son); } } } void tree::direct_direction(node* curr) { std::cout << curr->data << " "; if (curr->left_son != NULL) { direct_direction(curr->left_son); if (curr->right_son != NULL) direct_direction(curr->right_son); } else { if (curr->right_son != NULL) { direct_direction(curr->right_son); } } } void tree::reverse_direction(node* curr) { if (curr->left_son != NULL) { reverse_direction(curr->left_son); if (curr->right_son != NULL) reverse_direction(curr->right_son); std::cout << curr->data << " "; } else { if (curr->right_son != NULL) { reverse_direction(curr->right_son); } std::cout << curr->data << " "; } } int main() { tree x; srand(time(NULL)); int size; std::cout << "enter size of tree: "; std::cin >> size; x.generate_random_tree(size); //x.head->data = 5; //x.head->add_left_son(1); //x.head->left_son->add_right_son(2); //x.head->add_right_son(3); //x.head->right_son->add_right_son(4); std::cout << "Tree in symetric view: "; x.symetric_direction(x.head); std::cout << std::endl; std::cout << "Tree in reverse view: "; x.reverse_direction(x.head); std::cout << std::endl; std::cout << "Tree in direct view: "; x.direct_direction(x.head); std::cout << std::endl; tree y = x.mirror(x.head); std::cout << "Tree in symetric view: "; x.symetric_direction(x.head); std::cout << std::endl; std::cout << "Tree in reverse view: "; x.reverse_direction(x.head); std::cout << std::endl; std::cout << "Tree in direct view: "; x.direct_direction(x.head); std::cout << std::endl; return 0; } #include <iostream> #include <ctime> #include <cstdlib> #include "node.h" node::node() { father = NULL; left_son = NULL; right_son = NULL; data = 0; } void node::add_left_son(int x) { left_son = new node(); left_son->father = this; left_son->data = x; } void node::add_left_son() { left_son = new node(); left_son->father = this; } void node::add_right_son(int x) { right_son = new node(); right_son->father = this; right_son->data = x; } void node::add_right_son() { right_son = new node(); right_son->father = this; } void node::remove_left_son() { if (left_son->left_son == NULL && left_son->right_son == NULL) { delete left_son; left_son = NULL; } } void node::remove_right_son() { if (right_son->left_son == NULL && right_son->right_son == NULL) { delete right_son; right_son = NULL; } } void node::set_random_data() { data = rand() % 10; } class node { public: node(); void add_left_son(int x); void add_left_son(); void remove_left_son(); void remove_right_son(); void add_right_son(int x); void add_right_son(); void set_random_data(); int data; node* father; node* left_son; node* right_son; };