Міністерство освіти і науки України Національний університет „Львівська політехніка” Кафедра ЕОМ Звіт з лабораторної роботи № 5 з дисципліни: “Програмування” на тему: Структура даних „Бінарне дерево пошуку” Варіант 6 1. Мета роботи Навчитись працювати з структурою даних “Бінарне дерево пошуку ”. 2. Постановка задачі Побудувати бінарне дерево пошуку для послідовності чисел, що вводяться з клавіатури. Виконати обхід дерева у заданому порядку і підрахувати: кількість вершин дерева, що обраховується при проходженні дерева у прямому порядку; кількість листків дерева, що обраховується при проходженні дерева у зворотньому порядку; кількість вузлів, які мають тільки одного нащадка, що обраховується при проходженні дерева у симетричному порядку. Побудувати два бінарних дерева пошуку. Визначити, чи можна одне дерево одержати з іншого шляхом вилучення однієї вершини. 3. Алгоритм розв’язання задачі Ініціалізувати бінарне дерево пошуку№1 Вивести на екран рядок “Enter tree #1:” Вивести на екран рядок “Enter int element (0 - finish):” Ввести з клавіатури число x Якщо x≠0, то додати x в бінарне дерево пошуку№1 Якщо x≠0, то перейти до пункту 3 Роздрукувати бінарне дерево пошуку№1 Вивести на екран кількість вершин, листків, вузлів, які мають тільки одного нащадка, для бінарного дерева пошуку№1 Ініціалізувати бінарне дерево пошуку№2 Вивести на екран рядок “Enter tree #2:” Вивести на екран рядок “Enter int element (0 - finish):” Ввести з клавіатури число x Якщо x≠0, то додати x в бінарне дерево пошуку№2 Якщо x≠0, то перейти до пункту 11 Роздрукувати бінарне дерево пошуку№2 Вивести на екран кількість вершин, листків, вузлів, які мають тільки одного нащадка, для бінарного дерева пошуку№2 Якщо з бінарного дерева пошуку№1 можна видалити якусь вершину, і при цьому воно співпаде з бінарним деревом пошуку№2 або якщо з бінарного дерева пошуку№2 можна видалити якусь вершину, і при цьому воно співпаде з бінарним деревом пошуку№1, то вивести на екран рядок “Yes”, в іншому разі вивести на екран рядок “No” 4. Текст програми #include <stdio.h> #include "pBTREE.c" void MakeCopyTree(binary_tree rootF,binary_tree * rootT); void DestroyTree(binary_tree root); int NumPeaks(binary_tree root, binary_tree knot){ int num=0; if (knot) { if (WhoFather(root,knot)&&(WhoLeft(knot)||WhoRight(knot))) num++; num+=NumPeaks(root,WhoLeft(knot)); num+=NumPeaks(root,WhoRight(knot)); }; return num; } int NumLeafs(binary_tree knot){ int num=0; if (knot){ num+=NumLeafs(WhoLeft(knot)); num+=NumLeafs(WhoRight(knot)); if ((!WhoLeft(knot))&(!WhoRight(knot))) num++; } return num; } int NumElem(binary_tree knot){ int num=0; if (knot){ num+=NumElem(WhoLeft(knot)); num++; num+=NumElem(WhoRight(knot)); } return num; } int GoSym(binary_tree knot){ int num=0; if (knot){ num+=GoSym(WhoLeft(knot)); if (NumElem(knot)==2) num++; num+=GoSym(WhoRight(knot)); } return num; } int TreesEq(binary_tree root1,binary_tree root2){ if ((!root1)&&(!root2)) return 1; if ((root1)&&(root2)){ if (root1->data!=root2->data) return 0; if (!TreesEq(WhoLeft(root1),WhoLeft(root2))) return 0; if (!TreesEq(WhoRight(root1),WhoRight(root2))) return 0; return 1; } return 0; } int Test1(binary_tree root1,binary_tree root2,binary_tree knot){ int data1,ret; binary_tree btt; if (knot){ if (WhoFather(root1,knot)&&(WhoLeft(knot)||WhoRight(knot))){ MakeCopyTree(root1,&btt); data1=knot->data; DeleteSearchTree(&btt, data1); ret=0; if (TreesEq(btt,root2)) ret=1; DestroyTree(btt); if (ret) return 1; } if (Test1(root1,root2,WhoLeft(knot))) return 1; if (Test1(root1,root2,WhoRight(knot))) return 1; } return 0; } void DestroyTree(binary_tree root){ if (root){ DestroyTree(WhoLeft(root)); DestroyTree(WhoRight(root)); free(root); } } void MakeCopyTreeH(binary_tree rootF,binary_tree * rootT){ if (rootF){ *rootT=MakeNode(rootF->data); MakeCopyTreeH(WhoLeft(rootF),&((*rootT)->leftson)); MakeCopyTreeH(WhoRight(rootF),&((*rootT)->rightson)); } else { *rootT=NULL; } } void MakeCopyTree(binary_tree rootF,binary_tree * rootT){ Init(rootT); MakeCopyTreeH(rootF,rootT); } int main(void){ binary_tree bt1,bt2; int x; //Tree 1 Init(&bt1); printf("Enter tree #1:\n"); do { printf("Enter int element (0 - finish):"); scanf("%d",&x); if (x) AddSearchTree(&bt1,x); } while (x); PrintTurningTree(bt1,0); printf("Number of peaks:%d\n",NumPeaks(bt1,bt1)); printf("Number of leafs:%d\n",NumLeafs(bt1)); printf("Number of knots with 1 descendant:%d\n",GoSym(bt1)); //Tree 2 Init(&bt2); printf("Enter tree #2:\n"); do { printf("Enter int element (0 - finish):"); scanf("%d",&x); if (x) AddSearchTree(&bt2,x); } while (x); PrintTurningTree(bt2,0); printf("Number of peaks:%d\n",NumPeaks(bt2,bt2)); printf("Number of leafs:%d\n",NumLeafs(bt2)); printf("Number of knots with 1 descendant:%d\n",GoSym(bt2)); if (Test1(bt1,bt2,bt1)||Test1(bt2,bt1,bt2)) printf("Yes\n"); else printf("No\n"); return 0; } 5. Результати виконання програми Enter tree #1: Enter int element (0 – finish):1 Enter int element (0 – finish):2 Enter int element (0 – finish):3 Enter int element (0 – finish):0 3 2 1 Number of peaks:1 Number of leafs:1 Number of knots with 1 descendant:1 Enter tree #2: Enter int element (0 – finish):1 Enter int element (0 – finish):3 Enter int element (0 – finish):0 3 1 Number of peaks:0 Number of leafs:1 Number of knots with 1 descendant:1 Yes 6. Графічне представлення Бінарне дерево пошуку№1 Бінарне дерево пошуку№2    root↓  free↓   free↓  root↓  індекси 0 1 2 3 4 5 індекси 0 1 2 3 4 5  data 0 2 1 6 3 7 data 0 3 4 3 5 1  father 0 2 0 5 1 0 father 0 5 0 4 2 0  leftson 0 0 0 0 0 0 leftson 0 0 0 0 0 0  rightson 0 4 1 0 0 3 rightson 0 0 4 0 3 1  7. Висновки З допомогою цієї лабораторної роботи я навчився працювати з структурою даних “Бінарне дерево пошуку ”.