Міністерство освіти і науки України Національний Університет « Львівська Політехніка» Кафедра ЕОМ Звіт до лабораторної роботи №5 на тему: « Структура даних „БІНАРНЕ ДЕРЕВО ПОШУКУ”.» Варіант 4. Львів-2007 Назва роботи: Структури даних “Бінарне дерево пошуку”. Мета роботи: Закріпити теоретичні знання та оволодіти практичними навиками опрацювання структур даних “Бінарне дерево пошуку”. Засвоїти техніку створення та опрацювання складних типів даних. Теоретична частина: Деревом називається множина взаємно-зв’язаних елементів які називаються вузлами розташованих по рівнях. Бінарне дерево- це скінченна множина вузлів кожен з яких або порожній, або складається з кореня пов’язаного з двома різними бінарними деревами які називається лівим і правим піддеревом. Виконання роботи Завдання: Побудувати бінарне дерево пошуку для послідовності чисел, що вводяться з клавіатури. Виконати обхід дерева у заданому порядку і підрахувати: кількість вершин дерева, що обраховується при проходженні дерева у прямому порядку; кількість листків дерева, що обраховується при проходженні дерева у зворотньому порядку; кількість вузлів, які мають тільки одного нащадка, що обраховується при проходженні дерева у симетричному порядку. Вилучити з дерева всi вузли, що мають по два нащадки . #include <stdio.h> #include <conio.h> #include "pBTREE.c" void DelKnot(btree _tree); void main () { btree b,b1,b2 = NULL; Init(&b); Init(&b1); int i,n,k,j = 0; bool boo; printf("how much?\n"); scanf("%d",&n); printf("1-st element:\n"); scanf("%d",&k); MakeKnot(&b,k); for ( i = 0; i < n-1; i++) { boo = true; b1 = b; printf("Next: "); scanf("%d",&k); while(boo) { if( k >= b1->data) { if (WhoRight(b1)) b1 = WhoRight(b1); else boo = false; } else { if (WhoLeft(b1)) b1 = WhoLeft(b1); else boo = false; } } if (k >= b1->data) PutRight(b1,k); else PutLeft(b1,k); } GoSymmetric(b); PrintLevel(b,20,1); printf("\n"); DelKnot(b); printf("\n"); GoSymmetric(b); PrintLevel(b,20,1); printf("\n"); } void DelKnot(btree _tree) { if (_tree) { DelKnot(WhoLeft(_tree)); DelKnot(WhoRight(_tree)); if ((WhoLeft(_tree))&&(WhoRight(_tree))) Delete(&_tree, _tree->data); } return; } Результат виконання
Висновок: Закріпив теоретичні знання та оволодв практичними навиками опрацювання структур даних “Бінарне дерево пошуку”. Засвоїв техніку створення та опрацювання складних типів даних.