Міністерство освіти і науки України Національний Університет « Львівська Політехніка» Кафедра ЕОМ Звіт до лабораторної роботи №5 на тему: « Структура даних „БІНАРНЕ ДЕРЕВО ПОШУКУ”.» Варіант 7. Львів-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); int Compare(binary_tree root1,binary_tree root2); 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; int mas1[100],i=0; void main() { int z,k=0; double ser=0; binary_tree t1,p ; int x; unsigned i,n; Init(&t1); printf("Enter the number of knots of binary tree 1: "); 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; i=0; GoReverse(t1); //kilkist lustkiv pru zvorotniomy z=kil; printf("\nkilkist lustkiv=%d",z); printf("\n"); for(k=0;k<z;k++) ser+=mas1[k]; ser/=z; printf("seredne znachenna lustkiv = %.2lf\n",ser); PrintLevel(t1,20,1); 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(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; } // ????????? ??????? ??? ??????? Find 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++; mas1[i]=root->data; i++; } }; } // ????????? ??????? ??? ??????? 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, 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); } // ????????? ??????? ??? ??????? 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, 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); }; } // ??????? ?????? ?? ? ?????????? ??????? (??????????? ??????? ?????? ????????) // ??????? ????????????: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(" %d",root->data); PrintLevel(WhoLeft(root),k/2,i-k); PrintLevel(WhoRight(root),k/2,i+k); }; return; } 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(" %d\n",root->data); PrintTurningTree(WhoLeft(root),h+1); }; } Результат виконання Enter the number of knots of binary tree 1: 4 8 9 3 8 8 3 9 8 kilkist vyzliv=4 3 8 8 9 kilkist vyzliv z 1 nashcadkom=1 3 8 9 8 kilkist lustkiv=2 seredne znachenna lustkiv= 5.50 8 3 9 8 Висновок: Закріпила теоретичні знання та оволоділа практичними навиками опрацювання структур даних “Бінарне дерево пошуку”. Засвоїла техніку створення та опрацювання складних типів даних.