Міністерство освіти і науки України Національний університет "Львівська політехніка" Кафедра "Інформаційні системи та мережі"    Лабораторна робота № 7 з предмету: Алгоритми і структури даних на тему: Дерева. Бінарні дерева. Пошук          ЛЬВІВ-2008  Тема: Дерева. Бінарні дерева. Пошук. Мета роботи: Набуття навичок програмування дерев. Постановка завдання: Розробити засоби динамічного збереження дерев та виконання дій над ними згідно варіанту Варіант індивідуального завдання: Перевірити, чи двійкове дерево є збалансованим. Текст програми на мові С++: #include <stdio.h> #include <stdlib.h> #include <conio.h> struct minmax{ int min, max; }; class btree { public: int val; btree *left, *right; public: btree(int nval=0) { val=nval; left=NULL; right=NULL; } void show(int level=0) { if(level==0)printf("{\n"); for(int i=0; i<level; i++) putch(' '); printf("%d\n", val); if(left)left->show(level+1); if(right)right->show(level+1); if(level==0)printf("}\n"); } ~btree() { if(left) delete left; if(right) delete right; } }; btree *form(int level) { if(level==0)return NULL; btree *temp=new btree(random(50)); if(random(10)!=0)temp->left=form(level-1); if(random(10)!=0)temp->right=form(level-1); return temp; } struct minmax getminmax(btree *bt) { struct minmax m, m1={0, 0}, m2={0, 0}; if(bt->left) m1=getminmax(bt->left); if(bt->right) m2=getminmax(bt->right); m.min=(m1.min<m2.min)?m1.min:m2.min; m.max=(m1.max>m2.max)?m1.max:m2.max; m.min++; m.max++; return m; } int isbalanced(btree *bt) { struct minmax m=getminmax(bt); return (m.max-m.min<=1); } int main() { btree *bt; randomize(); clrscr(); puts("Forming binary tree:"); bt=form(3); bt->show(); printf("The binary tree is %s\n", isbalanced(bt)?"balanced" :"not balansed"); struct minmax m=getminmax(bt); printf("min=%d max=%d\n", m.min, m.max); getch(); return 0; } Результати компютерної реалізації програми: Нижче наведено скріншот роботи програми:
Висновки Під час виконання роботи я закріпив практичні навички роботи з рекурсивними функціями.