Ir para o conteúdo
  • Revista PROGRAMAR: Já está disponível a edição #60 da revista programar. Faz já o download aqui!

silulem

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

Mensagens Recomendadas

silulem

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;
}

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!

Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.

Entrar Agora

×

Aviso Sobre Cookies

Ao usar este site você aceita os nossos Termos de Uso e Política de Privacidade. Este site usa cookies para disponibilizar funcionalidades personalizadas. Para mais informações visite esta página.