Arvore Algoritmos avançados

Prévia do material em texto

#include <iostream>
using namespace std;
struct no{
int x;
no* dir;
no* esq;
};
no *raiz=NULL;
no *pai=NULL;
int nivel=0;
no*criaNo(int y);
void pre(no *pt);
void pos(no *pt);
void sim(no *pt);
void insere(no *pt, int z);
void busca(no*ptr,int t);
int main() 
{
	int valor;
	do{
 		cout<<"Entre com um valor inteiro para inserir um noh ou 0 para terminar: ";
		cin>>valor;
 		if(valor)insere(raiz,valor);
	}while(valor);
	
	cout<<"pre: ";
 	pre(raiz);cout<<endl;
	cout<<"pos: ";
 	pos(raiz);cout<<endl;
	cout<<"sim: ";
 	sim(raiz);cout<<endl;
 	do{
	 	cout<<"\nEntre com o numero a ser buscado: ";
		cin>>valor;
		nivel=0;
		if(valor)
		{
 			busca(raiz,valor);
			if(raiz->x==valor) 
			{cout<<" Eh a raiz da arvore.";}
			
			else if(pai==NULL)cout<<" \nNumero nao pertece a arvore";
			
 			 	else{	cout<<"\nO num esta no nivel "<<nivel<<" seu pai eh "<<pai->x;
 			 			if(pai->esq!=NULL) cout<<", cujo filho esquedo eh "<<pai->esq->x;
 			 			if(pai->dir!=NULL) cout<<" e cujo filho direito eh "<<pai->dir->x;
			 	}
		}
	} while(valor);
return 0;
}
no*criaNo(int y)
{
	no *p=new no;
	p->x=y;
	p->dir=NULL;
	p->esq=NULL;
	return p;
}
void insere(no *pt, int z)
{
	no *aux=pt;
	if (aux==NULL)raiz=criaNo(z);
	else{
 			if(aux->x>z){
 				if(aux->esq==NULL)aux->esq=criaNo(z);
				else insere(aux->esq,z);
 			}
 			if(aux->x<z){
 			if(aux->dir==NULL)aux->dir=criaNo(z);
			else insere(aux->dir,z);
 			}
	}
}
void busca(no*ptr,int t)
{
	no *aux=ptr;
	if (aux==NULL){cout<<"\n Arvore vazia\n";return;}
	else{
 			if(aux->x==t){return;}
 			else if((aux->x>t)&&(aux->esq!=NULL))
			 	{
				 nivel++;
				 if(aux->esq)pai=aux;
			 	 else pai=aux->esq;busca(aux->esq,t);
				}
 				else if((aux->x<t)&&(aux->dir!=NULL))
				 {
				 	nivel++;
				 	if(aux->dir)pai=aux;
				 	else pai=aux->dir;busca(aux->dir,t);
				}
 			return;
	}
}
void pre(no *pt)
{
	cout<<pt->x<<" ";
	if (pt->esq != NULL) pre(pt->esq);
	if (pt->dir != NULL) pre(pt->dir);
}
void pos(no *pt)
{
	if (pt->esq != NULL) pos(pt->esq);
	if (pt->dir != NULL) pos(pt->dir);
	cout<<pt->x<<" ";
}
void sim(no *pt)
{
	if (pt->esq != NULL) sim(pt->esq);
	cout<<pt->x<<" ";
	if (pt->dir != NULL) sim(pt->dir);
}