Лабораторная работа №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);
}
Скрины.