Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Структура даних „БІНАРНЕ ДЕРЕВО ПОШУКУ”.
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Електронні обчислювальні машини
Інформація про роботу
Рік:
2007
Тип роботи:
Лабораторна робота
Предмет:
Структура даних
Група:
КІ
Варіант:
15
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки України
Національний Університет « Львівська Політехніка»
Кафедра ЕОМ
Звіт
до лабораторної роботи №5
на тему: « Структура даних „БІНАРНЕ ДЕРЕВО ПОШУКУ”.»
Варіант 15.
Виконав:
ст. гр. КІ
Львів-2007
Назва роботи: Структури даних “Бінарне дерево пошуку”.
Мета роботи: Закріпити теоретичні знання та оволодіти практичними навиками опрацювання структур даних “Бінарне дерево пошуку”. Засвоїти техніку створення та опрацювання складних типів даних.
Теоретична частина:
Деревом називається множина взаємно-зв’язаних елементів які називаються вузлами розташованих по рівнях. Бінарне дерево- це скінченна множина вузлів кожен з яких або порожній, або складається з кореня пов’язаного з двома різними бінарними деревами які називається лівим і правим піддеревом.
Виконання роботи
Завдання:
Побудувати бінарне дерево пошуку для послідовності чисел, що вводяться з клавіатури. Виконати обхід дерева у заданому порядку і підрахувати:
кількість вершин дерева, що обраховується при проходженні дерева у прямому порядку;
кількість листків дерева, що обраховується при проходженні дерева у зворотньому порядку;
кількість вузлів, які мають тільки одного нащадка, що обраховується при проходженні дерева у симетричному порядку.
Знайти довжину мінімального шляху між листами.
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
typedef struct node
{
int data;
struct node *leftson, *rightson;
}*binary_tree;
void Init(binary_tree *root_ptr);
int Empty(binary_tree root);
binary_tree WhoRight(binary_tree tree_node);
void PutLeftLeft(binary_tree tree_node);
binary_tree Who(binary_tree root, int new_data);
void PutRight(binary_tree root, int new_data);
binary_tree Find(binary_tree root, int search_data);
int GoStraight(binary_tree root,int k,int z);
void GoSymmetric(binary_tree root);
void GoReverse(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, int new_data);
void DeleteSearchTree(binary_tree *root_ptr, int del_data);
void PrintLevel(binary_tree root, int k, int i);
void PrintTurningTree(binary_tree root, int h);
int kil=0;
void main()
{
int z,k=0;
binary_tree t1,p,p1 ;
int x,x1;
unsigned i,n;
Init(&t1);
printf("Enter the number of knots of binary tree: ");
scanf("%d",&n);
for (i=1;i<=n;i++)
{
scanf("%d",&x);
AddSearchTree(&t1, x);
};
printf("\n");
kil=0;
k=GoStraight(t1,k,0); //kilkist vyzliv pru priamomy prohodgenni
printf("\nkilkist vyzliv=%d",kil);
printf("\n");
kil=0;
GoSymmetric(t1); //kilkist vyzliv z 1 nashcadkom pru symetru4nomy
z=kil;
printf("\nkilkist vyzliv z 1 nashcadkom=%d",z);
printf("\n");
kil=0;
GoReverse(t1); //kilkist lustkiv pru zvorotniomy
z=kil;
printf("\nkilkist lustkiv=%d",z);
printf("\n");
PrintLevel(t1,20,1);
printf("\n");
puts("vvedit 2 vyzlu:");
scanf("%d%d",&x,&x1);
p=Find(t1,x);
p1=Find(t1,x1);
kil=0;k=0;
while(p!=NULL){
if(p1==p)
break;
while(p1!=NULL){
p1=WhoFather(t1,p1);
kil++;
if(p1==p)
break;
}
if(p1==p)
break;
p1=Find(t1,x1);
p=WhoFather(t1,p);
if(p1==p)
break;
kil=0;
k++;
}
//najmenshuj shliah - najmensha kilkist krokiv dvid 1 vyzla do 2
printf("najmenshuj shliah mig lustkamu = %d",kil+k);
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(int new_data)
{
binary_tree new_node;
new_node =(struct 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, int new_data)
{
binary_tree new_node;
new_node = MakeNode(new_data);
tree_node->leftson = new_node;
}
void PutRight(binary_tree tree_node, int new_data)
{
binary_tree new_node;
new_node = MakeNode(new_data);
tree_node->rightson = new_node;
}
void F(binary_tree root, int 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, int search_data)
{
binary_tree search_node = NULL;
F(root, search_data, &search_node);
return search_node;
}
int GoStraight(binary_tree root,int k,int z)
{
if (root)
{
k++;
printf(" %d", root->data);
kil++;
z=2;
k=GoStraight(WhoLeft(root),k,z);
z=1;
k=GoStraight(WhoRight(root),k,z);
k++;
}
else {
k=k-z;
}
return k;
}
void GoSymmetric(binary_tree root)
{
if (root)
{
GoSymmetric(WhoLeft(root));
printf(" %d", root->data);
if(root->leftson !=NULL && root->rightson == NULL || root->leftson ==NULL && root->rightson != NULL)
kil++;
GoSymmetric(WhoRight(root));
};
}
void GoReverse(binary_tree root)
{
if (root)
{
GoReverse(WhoLeft(root));
GoReverse(WhoRight(root));
printf(" %d", root->data);
if(root->leftson ==NULL && root->rightson == NULL)
kil++;
};
}
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, int 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);
}
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, int 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);
};
}
void PrintLevel(binary_tree root, int k, int i)
{
char c;
if (root)
{
printf("\n");
for(c=1;c<=40+i;c++) printf(" ");
printf(" %d",root->data);
PrintLevel(WhoLeft(root),k/2,i-k);
PrintLevel(WhoRight(root),k/2,i+k);
};
return;
}
void PrintTurningTree(binary_tree root, int h)
{
int i;
if (root)
{
PrintTurningTree(WhoRight(root),h+1);
for (i=1;i<=h;i++) printf(" ");
printf(" %d\n",root->data);
PrintTurningTree(WhoLeft(root),h+1);
};
}
Результат виконання
Висновок:
Закріпив теоретичні знання та оволодв практичними навиками опрацювання структур даних “Бінарне дерево пошуку”. Засвоїв техніку створення та опрацювання складних типів даних.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора