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

SIAOD / Деревья / TREES

.CPP
Скачиваний:
7
Добавлен:
20.03.2015
Размер:
3.87 Кб
Скачать
#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);
}
Соседние файлы в папке Деревья