Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Бінарне дерево пошуку
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Кафедра ЕОМ
Інформація про роботу
Рік:
2007
Тип роботи:
Звіт
Предмет:
Структура даних
Група:
КІ-14
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки України
Національний університет „Львівська політехніка”
Кафедра ЕОМ
Звіт
до лабораторної роботи № 5
з програмування
на тему
Структура даних „Бінарне дерево пошуку”
Мета роботи: Навчитись працювати з структурою даних “Бінарне дерево пошуку ”.
Постановка задачі:
Побудувати бінарне дерево пошуку для послідовності чисел, що вводяться з клавіатури. Виконати обхід дерева у заданому порядку і підрахувати:
кількість вершин дерева, що обраховується при проходженні дерева у прямому порядку;
кількість листків дерева, що обраховується при проходженні дерева у зворотньому порядку;
кількість вузлів, які мають тільки одного нащадка, що обраховується при проходженні дерева у симетричному порядку.
Вилучити з дерева всi листки.
Текст програми:
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#define infotype int
#define printfspec "%d "
int t=0;
struct node
{
infotype data;
struct node *leftson, *rightson;
};
typedef struct node *binary_tree;
binary_tree del_node0;
void Init(binary_tree *root_ptr);
int Empty(binary_tree root);
binary_tree WhoLeft(binary_tree tree_node);
binary_tree WhoRight(binary_tree tree_node);
void PutLeft(binary_tree root, infotype new_data);
void PutRight(binary_tree root, infotype new_data);
binary_tree Find(binary_tree root, infotype search_data);
void GoStraight(binary_tree root);
void GoSymmetric(binary_tree root);
void GoReverse(binary_tree root);
void GoStraight11(binary_tree root);
binary_tree WhoFather(binary_tree root, binary_tree knot);
binary_tree WhoBrother(binary_tree root, binary_tree knot);
void AddSearchTree(binary_tree *root_ptr, infotype new_data);
void DeleteSearchTree(binary_tree *root_ptr, infotype del_data);
void PrintLevel(binary_tree root, int k, int i);
void PrintTurningTree(binary_tree root, int h);
void main()
{
binary_tree t1;
infotype x;
int i=0;
Init(&t1);
do
{
printf("Enter element of binary tree (0- break inputing elements: ");
scanf("%d",&x);
if(x)
AddSearchTree(&t1, x);
}
while(x);
printf("\n");
printf("\n");
printf("GoStraight\n");
GoStraight(t1);t--;
printf("\nKilkict vershyn %d",t);
t=0;
printf("\n");
printf("GoSymmetric\n");
GoSymmetric(t1);
printf("\nKilkict vuzliv jaki maiuti 1 nashchadka %d",t);
t=0;
printf("\n");
printf("GoReverse\n");
GoReverse(t1);
printf("\nKilkict lystkiv %d",t);
t=0;
printf("\n");
printf("Tree built:\n");
PrintLevel(t1,20,1);
printf("\n");
printf("Tree built:\n");
printf("\n");
PrintTurningTree(t1,5);
printf("\n");
printf(" derevo z vydalenymy lystkamy\n");
GoStraight11(t1); //vydalenja lystkiv
printf("Tree built:\n");
PrintLevel(t1,20,1);
printf("\n");
printf("Tree built:\n");
printf("\n");
PrintTurningTree(t1,5);
printf("\n");
getch();
return;
}
// Реалізація інтерфейсу обробки бінарного дерева (БД) пошуку
// Ініціалізація БД
void Init(binary_tree *root_ptr)
{
*root_ptr = NULL;
}
// Перевірка чи БД порожнє
int Empty(binary_tree root)
{
return root == NULL;
}
// Пошук лівого сина заданого вузла БД
binary_tree WhoLeft(binary_tree tree_node)
{
if (tree_node)
return tree_node->leftson;
else
return tree_node;
}
// Пошук правого сина заданого вузла БД
binary_tree WhoRight(binary_tree tree_node)
{
if (tree_node)
return tree_node->rightson;
else
return tree_node;
}
// Створення нового вузла БД із заданим значенням
binary_tree MakeNode(infotype new_data)
{
binary_tree new_node;
new_node = malloc(sizeof(struct node));
new_node->data = new_data;
new_node->leftson = new_node->rightson = NULL;
return new_node;
}
// Створення лівого сина заданого вузла БД
void PutLeft(binary_tree tree_node, infotype new_data)
{
binary_tree new_node;
new_node = MakeNode(new_data);
tree_node->leftson = new_node;
}
// Створення правого сина заданого вузла БД
void PutRight(binary_tree tree_node, infotype new_data)
{
binary_tree new_node;
new_node = MakeNode(new_data);
tree_node->rightson = new_node;
}
// Допоміжна функція для функції Find
void F(binary_tree root, infotype search_data, binary_tree *search_node_ptr)
{
if (root && !*search_node_ptr)
if (root->data == search_data)
*search_node_ptr = root;
else
{
F(WhoLeft(root), search_data, search_node_ptr);
F(WhoRight(root), search_data, search_node_ptr);
};
}
// Пошук у БД першого вузла із заданим значенням
binary_tree Find(binary_tree root, infotype search_data)
{
binary_tree search_node = NULL;
F(root, search_data, &search_node);
return search_node;
}
// Проходження всіх вузлів БД в прямому порядку
void GoStraight(binary_tree root)
{
if (root)
{
printf(printfspec, root->data);
if(root->leftson!=0||root->rightson!=0||root->leftson!=0&&root->rightson!=0)
t++;
GoStraight(WhoLeft(root));
GoStraight(WhoRight(root));
};
}
// Проходження всіх вузлів БД в симетричному порядку
void GoSymmetric(binary_tree root)
{
if (root)
{
GoSymmetric(WhoLeft(root));
printf(printfspec, root->data);
if(root->leftson!=0&&root->rightson==0||root->rightson!=0&&root->leftson==0)
t++;
GoSymmetric(WhoRight(root));
};
}
// Проходження всіх вузлів БД у зворотньому порядку
void GoReverse(binary_tree root)
{
if (root)
{
GoReverse(WhoLeft(root));
GoReverse(WhoRight(root));
printf(printfspec, root->data);
if(root->leftson==0&&root->rightson==0)
t++;
};
}
// Проходження всіх вузлів БД в прямому порядку
void GoStraight11(binary_tree root)
{
if (root)
{
if(root->leftson!=0)
{
if(root->leftson->leftson==0&&root->leftson->rightson==0)
{
del_node0=root->leftson;
root->leftson=0;
free(del_node0);
}
}
GoStraight11(WhoLeft(root));
if(root->rightson!=0)
{
if(root->rightson->leftson==0&&root->rightson->rightson==0)
{
del_node0=root->rightson;
root->rightson=0;
free(del_node0);
}
}
GoStraight11(WhoRight(root));
};
}
// Допоміжна функція для функції WhoFather
void WhoF(binary_tree root, binary_tree tree_node, binary_tree *father)
{
if (root && !*father)
{
if (WhoLeft(root) == tree_node || WhoRight(root) == tree_node)
*father = root;
else
{
WhoF(WhoLeft(root), tree_node, father);
WhoF(WhoRight(root), tree_node, father);
};
};
}
// Пошук батька заданого вузла БД
binary_tree WhoFather(binary_tree root, binary_tree tree_node)
{
binary_tree father = NULL;
if (root != father)
WhoF(root, tree_node, &father);
return father;
}
// Пошук брата заданого вузла БД
binary_tree WhoBrother(binary_tree root, binary_tree tree_node)
{
if (WhoLeft(WhoFather(root, tree_node)) == tree_node)
return WhoRight(WhoFather(root, tree_node));
else
return WhoLeft(WhoFather(root, tree_node));
}
// Додавання вузла із заданим значенням в бінарне дерево пошуку
void AddSearchTree(binary_tree *root_ptr, infotype new_data)
{
if (!*root_ptr)
*root_ptr = MakeNode(new_data);
else
if (new_data < (*root_ptr)->data)
AddSearchTree(&((*root_ptr)->leftson), new_data);
else
AddSearchTree(&((*root_ptr)->rightson), new_data);
}
// Допоміжна функція для функції DeleteSearchTree
void Del(binary_tree *root_ptr, binary_tree *del_node_ptr)
{
if (WhoLeft(*root_ptr))
Del(&((*root_ptr)->leftson), del_node_ptr);
else
{
(*del_node_ptr)->data = (*root_ptr)->data;
*del_node_ptr = *root_ptr;
*root_ptr = WhoRight(*root_ptr);
};
}
// Вилучення вузла із заданим значенням з бінарного дерева пошуку
void DeleteSearchTree(binary_tree *root_ptr, infotype del_data)
{
binary_tree del_node;
if (*root_ptr)
if (del_data < (*root_ptr)->data)
DeleteSearchTree(&((*root_ptr)->leftson), del_data);
else
if (del_data > (*root_ptr)->data)
DeleteSearchTree(&((*root_ptr)->rightson), del_data);
else
{
del_node = *root_ptr;
if (!del_node->rightson)
*root_ptr = WhoLeft(del_node);
else
if (!WhoLeft(del_node))
*root_ptr = WhoRight(del_node);
else Del(&del_node->rightson, &del_node);
free(del_node);
};
}
// Роздрук вузлів БД у звичайному вигляді (обмежується шириною екрану монітора)
// Приклад використання:PrintLevel(Tree,20,1);
void PrintLevel(binary_tree root, int k, int i)
{
char c;
if (root)
{
printf("\n");
for(c=1;c<=40+i;c++) printf(" ");
printf(printfspec,root->data);
PrintLevel(WhoLeft(root),k/2,i-k);
PrintLevel(WhoRight(root),k/2,i+k);
};
return;
}
// Роздрук вузлів БД у перевернутому на 90 градусів вигляді
// Приклад використання: PrintTurningTree(Tree,2,1)
void PrintTurningTree(binary_tree root, int h)
{
int i;
if (root)
{
PrintTurningTree(WhoRight(root),h+1);
for (i=1;i<=h;i++) printf(" ");
printf(printfspec"\n",root->data);
PrintTurningTree(WhoLeft(root),h+1);
};
}
Графічне представлення бінарного дерева пошуку на базі масиву:
згенерований
індекси
0
1
2
3
4
5
6
7
8
9
10
11
12
13
data
0
5
3
2
3
4
7
3
6
1
4
5
8
9
father
0
6
5
1
2
0
0
10
5
3
3
8
6
12
leftson
0
3
0
9
0
2
1
0
11
0
7
0
0
0
rightson
0
0
4
10
0
8
12
0
0
0
0
0
13
0
б) після видалення листків
індекси
0
1
2
3
4
5
6
7
8
9
10
11
12
13
data
0
5
3
2
3
4
7
3
6
1
4
5
8
9
father
0
6
5
1
2
0
0
4
5
2
3
8
6
8
leftson
0
3
9
0
0
2
1
0
11
0
0
0
0
0
rightson
0
0
4
10
7
8
12
0
13
0
0
0
0
0
3-елементи дерева даних;
3-елементи дерева вільних комірок масиву;
Результати виконання програми.:
Висновок: На дані лабораторні роботі я навчився працювати з структурами даних бінарні дерева пошуку. Освоїв роботу з даними підпрограмами.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора