Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки України
Національний університет "Львівська політехніка"
Кафедра "Інформаційні системи та мережі"
Лабораторна робота № 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;
}
Результати компютерної реалізації програми:
Нижче наведено скріншот роботи програми:
Висновки
Під час виконання роботи я закріпив практичні навички роботи з рекурсивними функціями.
Ви не можете залишити коментар. Для цього, будь ласка, увійдіть
або зареєструйтесь.
Ділись своїми роботами та отримуй миттєві бонуси!
Маєш корисні навчальні матеріали, які припадають пилом на твоєму комп'ютері? Розрахункові, лабораторні, практичні чи контрольні роботи — завантажуй їх прямо зараз і одразу отримуй бали на свій рахунок! Заархівуй всі файли в один .zip (до 100 МБ) або завантажуй кожен файл окремо. Внесок у спільноту – це легкий спосіб допомогти іншим та отримати додаткові можливості на сайті. Твої старі роботи можуть приносити тобі нові нагороди!