Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Структура даних ДЕРЕВО
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
КН
Кафедра:
Кафедра ЕОМ
Інформація про роботу
Рік:
2013
Тип роботи:
Звіт до лабораторної роботи
Предмет:
Програмування Частина III Структури даних та алгоритми
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки, молоді та спорту України
Національний університет “Львівська політехніка”
Кафедра ЕОМ
Звіт
з лабораторної роботи № 6
на тему:
" Структура даних ДЕРЕВО "
з дисципліни:
" Програмування. Частина III. Структури даних та алгоритми "
Вибір індивідуального завдання:
№ варіанта = [(11) + (86) ] % 20 + 1= 107 % 20 + 1 = 7 + 1 = 8
Варіант 8
Львів – 2013
Мета роботи
Вивчення абстрактної структури даних "Бінарне дерево пошуку". Набуття практичних навичок побудови дерева та використання його для розв'язання прикладних задач.
Постановка задачі
Побудувати бінарне дерево пошуку для послідовності чисел, що вводяться з клавіатури. Реалізувати операції додавання та вилучення вузлів з бінарного дерева пошуку. Виконати обхід дерева у заданому порядку та показати:
послідовність вершин дерева при проходженні його у прямому порядку;
послідовність листків дерева при проходженні його у зворотньому порядку;
послідовність вузлів, що мають тільки одного нащадка при проходженні дерева у симетричному порядку.
Виконати індивідуальне завдання згідно з варіантом.
Варіант 8 : Знайти середнє геометричне значення всіх вузлів дерева.
Динаміка вмісту БД пошуку
3.1. Послідовність 10 чисел
10 13 8 4 25 9 3 11 19 15
3.2. Схематичне зображення БД пошуку після обробки кожного числа з вхідної послідовності
addTree(15);
10
addTree(23);
10
13
addTree(18);
10
8 13
addTree(7);
10
8 13
4
addTree(23);
10
8 13
4 25
addTree(21);
10
8 13 4 9 25
3
addTree(20);
10
8 13
4 9 11 25
3
addTree(57);
10
8 13
4 9 11 25 3
addTree(3);
10
8 13
4 9 11 25 3 19
addTree(6);
10
8 13
4 9 11 25
3 19
15
Середнє геометричне дерева
geometricMean = 10 * 8 * 13 * 4 * 9 * 11 * 25 * 3 * 19 * 15 =
= 9,873
3.3. Реалізація БД пошуку на базі масиву розмірністю 17
Індекси
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Info
0
10
8
13
4
9
11
25
9
19
15
0
0
0
0
0
0
Father
0
0
1
1
2
2
3
3
4
7
9
0
11
12
13
14
15
Left_son
0
2
4
6
8
0
0
9
0
10
0
0
0
0
0
0
0
Right_son
0
3
5
7
0
0
0
0
0
0
0
12
13
14
15
16
0
3.4. Обхід БД пошуку
а) послідовність вершин дерева при проходженні його у прямому порядку
10 8 4 13 25 19
б) послідовність листків дерева при проходженні його у зворотньому порядку
3 9 11 15
в) послідовність вузлів, що мають тільки одного нащадка при проходженні дерева у симетричному порядку
4 19 25
Алгоритм розв’язання задачі
Для створення бінарного дерева пошуку спочатку необхідно створити структуру вузла дерева у класі, описати змінні класу, та вказівники. Реалізувати функції які потрібні для роботи із деревом:
addTree(); //додати елемент у дерево
delSearchNode(); //видалити шуканий вузол
clear(); //видаляє все дерево
printTree(); //роздрук дерева
geometricMean; // середнє геометричне всіх вузлів дерева
preorderWalk(); //прямий обхід дерева
postorderWalk(); //зворотній обхід дерева
symmetricalWalk(); //симетричний обхід дерева
Для додавання елементів у дерево необхідно описати функцію addTree(). Перший елемент, який буде записано у дерево стане коренем дерева, а решта елементів будуть додаватись у ті місця бінарного дерева пошуку за принципом: більші або рівні елементи вершині будуть записуватись у праве піддерево, менші елементи від вершини будуть записуватись у ліве піддерево.
Для видалення якогось конкретного елементу із дерева необхідно описати функцію delSearchNode(). Алгоритм видалення листка: при видаленні листка, батьку цього листка записується вказівник на 0, замість вказівника на цей листок. Алгоритм видалення вузла з одним нащадком: батьку вузла записується вказівник на нащадка цього вузла, а сам вузол видаляється. Алгоритм видалення вузла із двома нащадками: цей вузол треба замінити на крайній лівий вузол правого піддерева.
Для того, щоб знайти середнє геометричне, слід всі вузли дерева помножити, а потім з результату добути корінь n-ної степені (n – кількість вузлів).
Текст програми
#include <iostream>
#include <windows.h>
#include <locale>
using namespace std;
template <class Type>
class Tree
{
struct Node{
Type data;
Node *left_son, *right_son;
};
Node *root;
int count;
public:
Tree(){root=NULL;};
~Tree(){clear();};
void addTree(Type obj){
root=_addTree(root, obj);
}
Node *_addTree(Node *temp, Type obj){
if(temp==0){
temp=new Node;
temp->data=obj;
temp->left_son=temp->right_son=NULL;
}
else if(obj<temp->data){
temp->left_son=_addTree(temp->left_son, obj);
}
else{
temp->right_son=_addTree(temp->right_son, obj);
}
return temp;
}
void delSearchNode(Type obj){
if(root==0) cout<<"Дерево пустое"<<endl;
else root=_delSearchNode(root, obj);
}
Node *_delSearchNode(Node *temp, Type obj){
if(temp==0) return temp;
if(obj<temp->data){
if(temp->left_son==0)
cout<<"Искомого элемента не существует"<<endl;
temp->left_son=_delSearchNode(temp->left_son, obj);
}
if(obj>temp->data){
if(temp->right_son==0)
cout<<"Искомого элемента не существует"<<endl;
temp->right_son=_delSearchNode(temp->right_son, obj);
}
if(obj==temp->data){
Node *current=temp;
if(temp->right_son==0 && temp->left_son==0){
delete current;
temp=NULL;
}
else if(temp->right_son==0){
Node *current=temp;
temp=temp->left_son;
delete current;
}
else if(temp->left_son==0){
Node *current=temp;
temp=temp->right_son;
delete current;
}
else{
if(temp->right_son->left_son==0){
Node *current=temp;
temp->right_son->left_son=temp->left_son;
temp=temp->right_son;
delete current;
}
else{
Node *current=temp;
current=current->right_son;
while(current->left_son->left_son){
current=current->left_son;
}
if(current->left_son->right_son==0){
Node *del_current=current->left_son;
temp->data=del_current->data;
current->left_son=NULL;
delete del_current;
}
else{
Node *del_current=current->left_son;
temp->data=del_current->data;
current->left_son=del_current->right_son;
delete del_current;
}
}
}
}
return temp;
}
void preorderWalk(void action(Node *)){
_preorderWalk(root, action);
}
void _preorderWalk(Node *temp, void action(Node *)){
if(temp==0) return;
action(temp);
_preorderWalk(temp->left_son, action);
_preorderWalk(temp->right_son, action);
}
void postorderWalk(void action(Node *)){
_postorderWalk(root, action);
}
void _postorderWalk(Node *temp, void action(Node *)){
if(temp==0) return;
_postorderWalk(temp->left_son, action);
_postorderWalk(temp->right_son, action);
action(temp);
}
void symmetricalWalk(void action(Node *)){
_symmetricalWalk(root, action);
}
void _symmetricalWalk(Node *temp, void action(Node *)){
if(temp==0) return;
_symmetricalWalk(temp->left_son, action);
action(temp);
_symmetricalWalk(temp->right_son, action);
}
static void delNode(Node *temp){delete temp;}
void clear(){_postorderWalk(root, delNode);}
static void printNode(Node *temp){
if(temp->left_son==0 && temp->right_son==0) return;
else cout<<temp->data<<" ";
}
static void printLeaf(Node *temp){
if(temp->left_son==0 && temp->right_son==0) cout<<temp->data<<" ";
else return;
}
static void printNode_oneSon(Node *temp){
if(temp->left_son==0){
if(temp->right_son!=0) cout<<temp->data<<" ";
else return;
}
if(temp->left_son!=0){
if(temp->right_son==0) cout<<temp->data<<" ";
else return;
}
}
void printTree(){
_printTree(root, 20, 0);
}
void _printTree(Node *temp, int width, int i){
if(temp==0) return;
else{
cout<<endl;
for(int k=0;k<40+i;k++) cout<<" ";
cout<<temp->data;
_printTree(temp->left_son, width/2, i-width);
_printTree(temp->right_son, width/2, i+width);
}
}
void printTurningTree(){
_printTurningTree(root, 0);
}
void _printTurningTree(Node *temp, int indent){
if(temp!=0){
_printTurningTree(temp->right_son, indent+1);
for(int i=0;i<indent;i++) printf(" ");
cout<<temp->data<<endl;
_printTurningTree(temp->left_son, indent+1);
}
}
void findParent(int x, int y){
_findParent(root, x, y);
}
void _findParent(Node *temp, int x, int y){
if(temp==0){
cout<<"Дерево пустое"<<endl;
return;
}
else{
if(x==root->data || y==root->data){
cout<<"У корня нету предка";
return;
}
if(temp->left_son!=0){
if(x==temp->left_son->data || y==temp->left_son->data){
cout<<temp->data<<endl;
return;
}
}
if(temp->right_son!=0){
if(x==temp->right_son->data || y==temp->right_son->data){
cout<<temp->data<<endl;
return;
}
}
if(x<temp->data && y<temp->data){
_findParent(temp->left_son, x, y);
}
if(x>temp->data && y>temp->data){
_findParent(temp->right_son, x, y);
}
if((x<temp->data && y>temp->data) || (x>temp->data && y<temp->data)){
cout<<temp->data<<endl;
return;
}
}
}
};
//---------------------------------------------------------------------------------
//---------------------------------------------------------------------------------
void main()
{
setlocale(LC_CTYPE,"Russian");
int N;
int elem, elem1, elem2, amount;
Tree <int> bt;
for(;;){
printf(
"\n Меню :"
"\n0. Выход"
"\n1. Заполнить дерево"
"\n2. Удалить узел"
"\n3. Распечатать дерево"
"\n4. Поиск общего предка двух узлов"
"\n5. Добавить элемент в дерево"
"\n\nВедите номер: ");
cin>>N;
switch(N){
case 0: exit(1);
case 1:
cout<<"Введите количество элементов: ";
cin>>amount;
cout<<"Введите элементы через пробел: ";
for(int i=0;i<amount;i++){
cin>>elem;
bt.addTree(elem);
}
break;
case 2:
cout<<"Какой элемент удалить: ";
cin>>elem;
bt.delSearchNode(elem);
break;
case 3:
bt.printTree();
cout<<"\nПрямой обход: ";
bt.preorderWalk(bt.printNode);
cout<<"\nОбратный обход: ";
bt.postorderWalk(bt.printLeaf);
cout<<"\nСимметричный обход: ";
bt.symmetricalWalk(bt.printNode_oneSon);
cout<<endl;
break;
case 4:
cout<<"Введите через пробел искомые узлы: ";
cin>>elem1>>elem2;
cout<<"Общий предок двух узлов: ";
bt.findParent(elem1, elem2);
break;
case 5:
cout<<"Ввудите элемент: ";
cin>>elem;
bt.addTree(elem);
break;
}
}
}
Результати виконання програми
/
Висновок
У цій лабораторній роботі я вивчив абстрактну структури даних "Бінарне дерево пошуку". Набув практичних навичок побудови дерева та провів дослідження його вмісту.
03.04.2018 21:04-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора