Jump to content

Método que retorna Os N Maiores números numa Arvore


silulem

Recommended Posts

Saudações,

Por Favor alguém que me ajude,

Tenho esta árvore abaixo, pediram-me para implementar o Metodo Pre-Ordem , Pos-Ordem e implementar um método que retorne os N maiores numero da Árvore abaixo.

O método Pre-Ordem e Pos-Ordem , já foram implementados , mas não consigo implementar o método que retorne maior numero da árvore.

Alguém pode ajudar-me.

//#include <iostream>
//using namespace std;
//classe arvore binaria de busca para valores inteiros
class CArvore
{
private:
 int * Raiz;
 CArvore * Esq, *Dir;
public:
CArvore();
CArvore(int raiz);
CArvore(int raiz, CArvore * esq, CArvore * dir);
void Adicionar(int elem);
bool Buscar(int elem);
bool EVazia();
void Eliminar(int elem);
void PreOrdem();
void PosOrdem();
void OrdemSimetrica();
CArvore& operator =(const CArvore&);
};
//------------------------------------------------------------ CONSTRUTORES
 CArvore:: CArvore()
 {
	 Raiz = NULL;
	 Esq = NULL;
	 Dir = NULL;
 }
//------------------------------------------------------------
 CArvore::CArvore(int raiz)
 {
	 Raiz = new int;
	 *Raiz = raiz;
	 Esq = new CArvore();
	 Dir = new CArvore();
 }
//--------------------------------------------------------------
 CArvore::CArvore(int raiz, CArvore * esq, CArvore * dir)
 {
	 Raiz = new int;
	 *Raiz = raiz;
	 Esq = esq;
	 Dir = dir;
 }
//---------------------------------------------------------------- ADICIONAR
 void CArvore::Adicionar(int elem)
 {
	 if(EVazia())
	 {
	 Raiz = new int;
	 *Raiz = elem;
	 Esq = new CArvore();
	 Dir = new CArvore();
	 }
	 else
	 {
	 if (elem < *Raiz)
	 Esq->Adicionar(elem);
	 else
	 Dir->Adicionar(elem);
	 }
 }
//---------------------------------------------------------------- BUSCAR
 bool CArvore::Buscar(int elem)
 {
 if(!EVazia())
	 {
	 if(elem == *Raiz)
		 return true;
	 else if(elem > *Raiz)
		 return Dir->Buscar(elem);
	 else
		 return Esq->Buscar(elem);
	 }
 else return false;
 }

//------------------------------------------------------------------- EVAZIA
 bool CArvore::EVazia()
 {
	 if(Raiz == NULL)
		 return true;
	 else return false;
 }
//---------------------------------------------------------------- ELIMINAR
void CArvore::Eliminar(int elem)
{
if(!EVazia())
{
 if(elem == *Raiz)
 {
CArvore* aux;
		 if(Esq->EVazia())
		 {
		 delete Esq;
 aux = Dir;
 *this = *aux;
 delete aux;
		 }
		 else
		 if(Dir->EVazia())
		 {
		 delete Dir;
 aux = Esq;
		 *this = *Esq;
 delete aux;
		 }
		 else
		 {
		 CArvore* sucessor = Dir;
		 while(!sucessor->Esq->EVazia())
			 sucessor = sucessor->Esq;
		 *Raiz = *sucessor->Raiz;
		 delete sucessor->Esq;
 aux = sucessor->Dir;
		 *sucessor = *sucessor->Dir;
 delete aux;
	 }
	 }
	 else
	 if(elem < *Raiz)
		 Esq->Eliminar(elem);
	 else
		 Dir->Eliminar(elem);
}
}
//--------------------------------------------------------------- Pré-ORDEM
 void CArvore::PreOrdem()
 {
	 if(!EVazia())
	 {
cout << *Raiz << ", ";
if(!Esq->EVazia())
	 Esq->PreOrdem();
	 if(!Dir->EVazia())
		 Dir->PreOrdem();
	 }
 }
//--------------------------------------------------------------- Pós-ORDEM
 void CArvore::PosOrdem()
 {
	 if(!EVazia())
	 {
	 if(!Esq->EVazia())
	 Esq->PosOrdem();
	 if(!Dir->EVazia())
		 Dir->PosOrdem();
	 cout << *Raiz << ", ";
	 }
 }
//--------------------------------------------------------------- ORDEM SIMETRICA
 void CArvore::OrdemSimetrica()
 {
	 if(!EVazia())
	 {
	 if(!Esq->EVazia())
	 Esq->OrdemSimetrica();
	 cout << *Raiz << ", ";
	 if(!Dir->EVazia())
		 Dir->OrdemSimetrica();
	 }
 }
//----------------------------------------------------------------- OPERADOR =
CArvore& CArvore::operator =(const CArvore& x)
 {
this->Raiz = x.Raiz;
Dir = x.Dir;
Esq = x.Esq;
return *this;
}

Link to post
Share on other sites
HappyHippyHippo

usas uma lista, depois é percorrer a árvore:

nota : não olhei para o código que fizeste, somente estou a escrever o algoritmo que necessitas

// pseudo código

função CArvore::nmaiores(lista, n) retorna lista {
 se Dir não for nulo
   então chamar "nmaiores" sobre a subárvore Dir

 se n for maior ou igual ao tamanho da lista
   insere o nó da árovore à cabeça da lista
   se Esq não for nulo e n for maior ou igual ao tamanho da lista
     então chamar "nmaiores" sobre a subárvore Esq

 retorna a lista
}

IRC : sim, é algo que ainda existe >> #p@p
Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.