Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:

SIAOD / Деревья / Деревья отчёт

.doc
Скачиваний:
7
Добавлен:
20.03.2015
Размер:
49.15 Кб
Скачать

Лабораторная работа №4.

Тема: Деревья.

#include <iostream.h>

#include <iomanip.h>

#include <stdlib.h>

#include <conio.h>

struct leaf{

int num;

leaf *left, *right;

};

class trees{

public:

void add(leaf *&t, int num);

void output(leaf *t, int level);

void Delete(leaf *&t);

leaf *search(leaf *t, int num);

void delx(leaf *&t, leaf *&root,int x);

void delr(leaf *&z, leaf *&q);

leaf* search2(leaf *t, leaf *f, int num);

};

void main(){

clrscr();

int n, num, level=0;

leaf *f;

trees object;

do{

clrscr();

cout<<"n=";

cin>>n;

}while(n<=0);

leaf *t;

t=NULL;

for(int i=1;i<=n;i++){

cout<<"num=";

cin>>num;

object.add(t, num);

}

object.output(t,level);

int exit=1;

while(exit == 1){

cout<<endl;

cout<<"1-Poisk"<<endl;

cout<<"2-dobavit'"<<endl;

cout<<"3-udalit' 1 element"<<endl;

cout<<"4 udalit' celuiu vetv'"<<endl;

cout<<"5-vivod"<<endl;

int chose;

cout<<"chose=";

cin>>chose;

switch(chose){

case 1:

cout<<"search num=";

cin>>num;

leaf *temp;

f=t;

temp=object.search(t, num);

if(temp == NULL)

cout<<"Chislo "<<num<<" ne naideno!"<<endl;

else

cout<<"Chislo "<<num<<" naideno!"<<endl;

break;

case 2:

cout<<"num=";

cin>>num;

object.add(t, num);

object.output(t,level);

break;

case 3:

cout<<"Udaliti chislo num=";

cin>>num;

object.delx(t, t, num);

object.output(t,level);

break;

case 4:

f=t;

cout<<"num=";

cin>>num;

leaf *f1=object.search2(t, f, num);

if(f1 == t){

object.Delete(t);

}

else if(f1->left->num == num){

object.Delete(f1->left);

f1->left=NULL;

}

else if(f1->right->num == num){

object.Delete(f1->right);

f1->right=NULL;

}

break;

case 5:

object.output(t,level);

break;

default:

exit=0;

}

}

getch();

object.Delete(t);

}

void trees::add(leaf *&t, int num){

if(t == NULL){

t=new leaf;

t->left=NULL;

t->right=NULL;

t->num=num;

}

else if(num < t->num)

add(t->left, num);

else if(num >= t->num)

add(t->right, num);

}

void trees::output(leaf *t, int level){

if(t == NULL){

cout<<"Your tree is empty";

return;

}

if(t->left != NULL)

output(t->left, level+1);

cout<<setw(level*4)<<t->num<<endl<<endl;

if(t->right != NULL)

output(t->right, level+1);

}

void trees::Delete(leaf *&t){

if(t == NULL){

cout<<endl<<"Tree is empty";

return;

}

if(t->left!=NULL)

Delete(t->left);

if(t->right!=NULL)

Delete(t->right);

delete t;

t=NULL;

}

leaf* trees::search(leaf *t, int num){

if(t == NULL){

cout<<endl<<"The number was not found!";

return NULL;

}

if(t->num == num)

return t;

if(num < t->num && t->left!=NULL)

return search(t->left, num);

if(num >= t->num && t->right!=NULL)

return search(t->right, num);

return NULL;

}

leaf* trees::search2(leaf *t, leaf *f, int num){

if(t == NULL){

cout<<endl<<"The number was not found!";

return NULL;

}

if(t->num == num)

return f;

if(num < t -> num && t -> left != NULL)

return search2(t -> left, f=t,num);

if(num >= t -> num && t -> right != NULL)

return search2(t -> right, f=t,num);

return NULL;

}

void trees::delx(leaf *&t, leaf *&root,int x){

leaf *q;

if(t == NULL)

cout<<"Tree is empty";

else{

if(x < t->num)

delx(t->left, root,x);

if(x > t->num)

delx(t->right, root,x);

if(x == t->num && t != root){

q=t;

if(t->right == NULL){

t=q->left;

delete q;

}

else if(t->left == NULL){

t=q->right;

delete q;

}

else

delr(q->left, q);

}

}

}

void trees::delr(leaf *&r, leaf *&q){

leaf *s;

if(r->right == NULL){

q->num=r->num;

q=r;

s=r;

r=r->left;

delete s;

}

else

delr(r->right, q);

}

Скрины.

Соседние файлы в папке Деревья