 |
Пример выполнения программы
|
|
|
|
ОТЧЕТ ПО ЛАБОРАТОРНОЙ РАБОТЕ № 4
Дисциплина: « Структуры и алгоритмы обработки данных »
Тема: «Программирование с использованием динамических структур: АВЛ-деревья»
ВЫПОЛНИЛ студент группы 14-ИТ-2
Кунцевич Н.А.
ПРОВЕРИЛА ст. преподаватель кафедры ТП
Деканова М.В.
Полоцк 2015 г.
Необходимо написать программу, которая демонстрирует работу с АВЛ-деревьями. Должны быть реализованы следующие методы:
· создание дерева;
· добавление узла;
· удаление узла;
· вывод элементов на экран одним из обходов;
· определение глубины дерева;
· удаление дерева.
При необходимости должна выполняться балансировка дерева.
Листинг программы:
#include <iostream>
#include "stdlib.h"
#include <locale.h>
using namespace std;
struct node
{
int key;
unsigned char height;
node* left;
node* right;
node(int k){ key = k; left = right = 0; height = 1; }
};
struct node *tree = NULL;
unsigned char height(node* p);
int bfactor(node* p);
void fixheight(node* p);
node* rotateright(node* p);
node* rotateleft(node* q);
node* balance(node* p);
node* Add(node* p, int k);
node* findmin(node* p);
node* Delete(node* p, int k);
void print(node *a);
void Menu();
int Depth(node *tree);
void DeleteTree(node *tree);
int main(void)
{
setlocale(LC_ALL, "Rus");
Menu();
system("pause");
return 0;
}
void Menu(void)
{
int value = 0;
while (1)
{
int menu = -1;
printf("1 добавить\t");
printf("2 удалить\t");
printf("3 Вывод \t");
printf("4 глубина\t");
printf("5 удалить дерево\n");
printf("0 Выход\n");
while (1){
fflush(stdin);
if (scanf("%d", &menu) == 1){
break;
}
else{
printf("Неверный ввод. Попробуйте снова...\n");
}
}
switch (menu){
case 1:{
system("cls");
printf("Введите элемент для добавления: ");
scanf("%d", &value);
tree = Add(tree,value);
printf("Готово! \n");
system("pause");
system("cls");
break;
}
case 2:{
system("cls");
printf("Выберите элемент для удаления: ");
scanf("%d", &value);
|
|
|
tree = Delete(tree,value);
printf("Готово! \n");
system("pause");
system("cls");
break;
}
case 3:{
system("cls");
print(tree);
system("pause");
system("cls");
break;
}
case 4:{
system("cls");
printf("Макс глубина: %d\n", Depth(tree));
system("pause");
system("cls");
break;
}
case 5:{
system("cls");
DeleteTree(tree);
printf("Дерево удалено\n");
tree = NULL;
system("pause");
system("cls");
break;
}
case 0:{
system("cls");
exit(0);
break;
}
default:{
system("cls");
printf("Неверный ввод. Попробуйте снова...\n");
break;
}
}
}
}
unsigned char height(node* p)
{
return p?p->height:0;
}
int bfactor(node* p)
{
return height(p->right)-height(p->left);
}
void fixheight(node* p)
{
unsigned char hl = height(p->left);
unsigned char hr = height(p->right);
p->height = (hl>hr?hl:hr)+1;
}
node* rotateright(node* p)
{
node* q = p->left;
p->left = q->right;
q->right = p;
fixheight(p);
fixheight(q);
return q;
}
node* rotateleft(node* q)
{
node* p = q->right;
q->right = p->left;
p->left = q;
fixheight(q);
fixheight(p);
return p;
}
node* balance(node* p)
{
fixheight(p);
if(bfactor(p)==2)
{
if(bfactor(p->right) < 0)
p->right = rotateright(p->right);
return rotateleft(p);
}
if(bfactor(p)==-2)
{
if(bfactor(p->left) > 0)
p->left = rotateleft(p->left);
return rotateright(p);
}
return p;
}
node* Add(node* p, int k) // вставка ключа k в дерево с корнем p
{
if(!p) return new node(k);
if(k<p->key)
p->left = Add(p->left,k);
else
p->right = Add(p->right,k);
return balance(p);
}
node* findmin(node* p) // поиск узла с минимальным ключом в дереве p
{
return p->left?findmin(p->left):p;
}
node* Deletemin(node* p) // удаление узла с минимальным ключом из дерева p
{
if(p->left==0)
return p->right;
p->left = Deletemin(p->left);
return balance(p);
}
node* Delete(node* p, int k) // удаление ключа k из дерева p
{
if(!p) return 0;
if(k < p->key)
p->left = Delete(p->left,k);
else if(k > p->key)
p->right = Delete(p->right,k);
else // k == p->key
{
node* q = p->left;
node* r = p->right;
delete p;
if(!r) return q;
node* min = findmin(r);
min->right = Deletemin(r);
min->left = q;
return balance(min);
}
return balance(p);
}
void print(node *a){
if(a!= NULL){
printf("%d\n", a->key);
print(a->left);
print(a->right);
}
}
int Depth(node *tree){
int depthLeft, depthRight, depthval;
if (tree == NULL)
depthval = -1;
else
{
depthLeft = Depth(tree->left);
depthRight = Depth(tree->right);
depthval = 1 + max(depthLeft, depthRight);
}
return depthval;
}
void DeleteTree(node *tree)
|
|
|
{
if(tree!= NULL){
DeleteTree(tree->left);
DeleteTree(tree->right);
free(tree);
}
}
ПРИМЕР ВЫПОЛНЕНИЯ ПРОГРАММЫ
При запуске появляется консольное окно с меню (рисунок 1):
Рис.1 – Главное меню
Пример добавления элементов в АВЛ-дерево представлен на рисунках 2,3:
Рис.2 – Ввод элемента
Рис.3 – Вывод добавленных элементов в АВЛ-дерево
Удаление элемента “6” продемонстрирован на рисунке 4:
Рис.4 – Удаление элемента
Вывод на экран продемонстрирован на рисунке 5:
Рис.5 – Вывод на экран после удаления
Вывод максимальной длины продемонстрирован на рисунке 6:
Рис.6 – Вывод максимальной длины
Удаление АВЛ-дерева продемонстрирован на рисунке 7:
Рис.7 – Удаление АВЛ-дерева
|
|
|
