МІНІСТЕРСТВО ОСВІТИ ТА НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА” Кафедра САПР Лабораторна робота №3 СТВОРЕННЯ I ВЕДЕННЯ БІНАРНИХ ДЕРЕВ з курсу: “Алгоритми и структури данних” Прийняв ЛЬВІВ 2007 Мета роботи Ознайомитися iз способом подання даних в оперативнiй пам'ятi ЕОМ у виглядi бінарних дерев. Оволодiти методами роботи iз бінарними деревами. Теоретичні відомості Для описання будь-якої структури, яка характеризується ієрархiчними зв'язками, є корисними дерева. Існує два типи схем, що використовуються у дослідженнях генеалогії. Перший тип називається схемою родоводу, другий - схемою нащадків. Якими б не були дерева, усі вони мають набір спільних властивостей. У кожному дереві є визначений вузол - корінь. Вузол, у якого немає нащадків, називається термінальним вузлом, або листом. Всі інші вузли називаються гілковими вузлами. Дерево - це визначена множина одного чи кількох вузлів, таких, що: Є спеціально визначений вузол, що називається коренем. Інші вузли є розділениними на підмножини, що не перетинаються Т1, Т2, Т3,..., Тn (n>=0), кожна з яких є деревом. Кожне Ті(1<=i<=n) називається піддеревом вузла. Рівнем вузла є 1 плюс довжина шляху до нього від кореня. Степенем вузла є кількість піддерев, які з нього виходять. Впорядкованим називається дерево, у якого вузли на кожному рівні впорядковані певним чином. Якщо видалити корінь із гілками, то отримується множина незв'язаних дерев. Кожен набір незв'язаних дерев називається лісом. Якщо степінь кожного вузла є меншим або дорiвнює 2, то дерево називається бінарним. Бінарним деревом називається множина m (m>=0) вузлів, що є або порожньою (m=0), або містить кореневий вузол, який має два незв'язаних бінарних піддерева, що називається лівим піддеревом і правим піддеревом. Бінарне дерево, у якого кожний вузол має степінь 0 чи 2, називається повністю бінарним деревом. Оскільки бінарні дерева легко зображати і маніпулювати з ними, зручно перетворити будь-яке дерево в еквівалентну бінарну форму (якщо можливо). Індивідуальне завдання Реалізувати бінарне дерево. Текст програми: #include <stdio.h> #include <stdlib.h> #include <conio.h> //-----DATA SRUCTURES---------- typedef char type_of_element; struct unit { type_of_element key; unit * left; unit * right; unit * parent; }; //---------------------------- void tree_insert(unit **, type_of_element); void inorder_tree_walk(unit *); unit * tree_search(unit *, type_of_element); unit * initialization_tree(void); unit * tree_minimum (unit *); unit * tree_successor(unit *); unit * tree_delete(unit *, unit *); //--------MAIN--------------- void main (void) { unit * root; root=initialization_tree(); type_of_element element; while (1) { printf ("\n 1 - add element\n2 - delete element\n 3 - show tree \n4 - exit \n"); int answer; scanf(" %d",&answer); switch (answer) { case 1:{ printf("\n Enter the key of current element\n"); scanf(" %c",&element); tree_insert(&root,element); }; break; case 2:{ type_of_element symbol; printf("\n Enter the key of element \n"); scanf(" %c",&symbol); tree_delete(root, tree_search(root, symbol)); }; break; case 3:{ inorder_tree_walk(root); }; break; default:{ printf("\n Good bye \n"); goto l1; } } } l1: getch(); } //----INSERTING FUNCTION------------- void tree_insert(unit ** root, type_of_element element) { unit * run_pointer,* pointer, * inserting_unit; pointer=(*root); run_pointer=NULL; //-----NEW UNIT------ inserting_unit=(unit *)malloc(sizeof(struct unit)); inserting_unit->left=NULL; inserting_unit->right=NULL; inserting_unit->parent=NULL; inserting_unit->key=element; //------------------- while (pointer!=NULL) { run_pointer=pointer; if (element<pointer->key) pointer=pointer->left; else pointer=pointer->right; } inserting_unit->parent=run_pointer; if (run_pointer==NULL) (*root)=inserting_unit; else if (inserting_unit->key<run_pointer->key) run_pointer->left=inserting_unit; else run_pointer->right=inserting_unit; } //-----INITIALIZATION OF TREE-------------- unit * initialization_tree (void) { unit * root; root=(unit *)malloc(sizeof(struct unit)); root->left=NULL; root->right=NULL; root->parent=NULL; printf("\n Enter the key of the root of tree\n"); type_of_element element; scanf(" %c",&element); root->key=element; if (root!=NULL) return root; else { printf("\n Error\n") ;return NULL;}; } //---INORDER TREE WALK-------- void inorder_tree_walk(unit * root) { if (root!=NULL) { inorder_tree_walk(root->left); printf(" %c",root->key); inorder_tree_walk(root->right); }; } //----------TREE MINIMUM-------------------------- unit * tree_minimum (unit * x) { while (x->left!=NULL) x=x->left; return x; } //------------TREE SUCCESSOR---------------------- unit * tree_successor(unit * x) { unit * y; if (x->right!=NULL) return tree_minimum(x->right); y=x->parent; while ((y!=NULL) && (x==y->right)) { x=y; y=y->parent;}; return y; } //-------------DELETE ELEMENT----------------------- unit * tree_delete(unit * root, unit * z) { unit * y, * x; if ((z->left==NULL) || (z->right==NULL)) y=z; else y=tree_successor(z); if (y->left!=NULL) x=y->left; else x=y->right; if (x!=NULL) x->parent=y->parent; if (y->parent==NULL) root=x; else if (y==y->parent->left) y->parent->left=x; else y->parent->right=x; if (y!=z) z->key=y->key; return y; } //--------TREE SEARCH--------------------- unit * tree_search(unit * pointer, type_of_element symbol) { if ((pointer==NULL)|| (pointer->key==symbol)) return pointer; if (symbol<pointer->key) tree_search(pointer->left,symbol); else tree_search(pointer->right,symbol); } Висновок Після виконаної роботи я ознайомився iз способом подання даних в оперативнiй пам'ятi ЕОМ у виглядi бінарних дерев та оволодів методами роботи iз бінарними деревами.