#include "Arvore.h"
#include <math.h>
Arvore::Arvore(){
raizPtr = NULL;
nivel = 0;
}
Arvore::~Arvore(){
}
void Arvore::setNivel(int valor)
{
nivel = valor;
}
void Arvore::cadastraCliente()
{
Cliente *novoCliente;
int chave;
string nome;
int idade;
cout << "\nDigite a chave do cliente a ser cadastrado: ";
cin >> chave;
cout <<"\nDigite o nome do cliente a ser cadastrado: ";
cin >> nome;
cout << "\nDigite a idade do cliente a ser cadastrado: ";
cin >> idade;
novoCliente = new Cliente(chave,nome,idade);
if(raizPtr == NULL)
{
raizPtr = novoCliente;
raizPtr->setClienteDireita(NULL);
raizPtr->setClienteEsquerda(NULL);
}
else
{
insereCliente(novoCliente, raizPtr);
}
}
void Arvore::insereCliente(Cliente *novoCliente, Cliente *auxiliar)
{
if(novoCliente->getChave() < auxiliar->getChave())
{
if(auxiliar->getClienteEsquerda() == NULL)
{
auxiliar->setClienteEsquerda(novoCliente);
}
else
{
insereCliente(novoCliente,auxiliar->getClienteEsquerda());
}
}
else if(novoCliente->getChave() >= auxiliar->getChave())
{
if(auxiliar->getClienteDireita() == NULL)
{
auxiliar->setClienteDireita(novoCliente);
}
else
{
insereCliente(novoCliente,auxiliar->getClienteDireita());
}
}
} //fim do método insereCliente
void Arvore::removeCliente()
{
Cliente *procurador = raizPtr;
int chaveDelete; //chave da árvore que será deletada
cout << "\nDigite a chave do cliente a ser removido: ";
cin >> chaveDelete;
if(existeCliente(chaveDelete,procurador))
{
deletarCliente(chaveDelete,raizPtr);
}
else
{
cout << "Cliente nao esta na arvore." << endl;
}
}//fim do método removeCliente
void Arvore::deletarCliente(int chave, Cliente *auxiliar)
{
Cliente *destruidorDoCliente; //irá deletar o cliente
if(chave > auxiliar->getChave())
{
deletarCliente(chave, auxiliar->getClienteDireita());
}
else if(chave < auxiliar->getChave())
{
deletarCliente(chave, auxiliar->getClienteEsquerda());
} else if(chave == auxiliar->getChave())
{
if(auxiliar->getClienteEsquerda() == NULL)
{
destruidorDoCliente = auxiliar;
auxiliar = auxiliar->getClienteDireita();
//cout << auxiliar->getChave();
delete destruidorDoCliente;
cout << raizPtr << endl;
cout << auxiliar;
}
else if(auxiliar->getClienteDireita() == NULL)
{
destruidorDoCliente = auxiliar;
auxiliar = auxiliar->getClienteEsquerda();
delete destruidorDoCliente;
}
else{
Cliente maiorDaEsquerda;
maiorDaEsquerda = getMaiorClienteDaEsquerda(auxiliar->getClienteEsquerda());
auxiliar->setNome(maiorDaEsquerda.getNome());
auxiliar->setIdade(maiorDaEsquerda.getIdade());
auxiliar->setChave(maiorDaEsquerda.getChave());
deletarCliente(maiorDaEsquerda.getChave(), auxiliar->getClienteEsquerda());
}
}
}
bool Arvore::existeCliente(int chaveDelete, Cliente *procurador){
if(procurador == NULL)
{
return false;
}
else if(chaveDelete < procurador->getChave())
{
return existeCliente(chaveDelete,procurador->getClienteEsquerda());
}
else if(chaveDelete > procurador->getChave())
{
return existeCliente(chaveDelete,procurador->getClienteDireita());
}
else
{
removePtr = procurador;
return true;
}
}
Cliente Arvore::getMaiorClienteDaEsquerda(Cliente *auxiliar){
while(auxiliar->getClienteDireita() != NULL){
auxiliar = auxiliar->getClienteDireita();
}
return *(auxiliar);
}
Cliente Arvore::getMaiorClienteDaDireita(Cliente *auxiliar){
while(auxiliar->getClienteDireita() != NULL){
auxiliar = auxiliar->getClienteDireita();
}
return *(auxiliar);
}
Cliente* Arvore::getRaiz()
{
return raizPtr;
}
void Arvore::localizaClientePorChave(){
int chave;
cout << "\nDigite a chave do cliente a ser localizado: ";
cin >> chave;
if(existeCliente(chave,raizPtr)){
Cliente *encontrado = encontrarCliente(chave,raizPtr);
cout << "\nChave: " << encontrado->getChave();
cout << "\nNome: " << encontrado->getNome();
cout << "\nIdade: " << encontrado->getIdade();
}
else{
cout << "\nNao ha cliente com essa chave na arvore.";
}
}
//Busca o cliente na arvore. So é chamado quando se tem certeza de que
//o cliente esta na árvore
Cliente* Arvore::encontrarCliente(int chaveCliente, Cliente *auxiliar){
if(chaveCliente < auxiliar->getChave()){
return encontrarCliente(chaveCliente, auxiliar->getClienteEsquerda());
}
else if(chaveCliente > auxiliar->getChave()){
return encontrarCliente(chaveCliente, auxiliar->getClienteDireita());
}
else{
return auxiliar;
}
}
void Arvore::numeroClientes(Cliente * aux, int *contador)
{
if(aux!=NULL)
{
*contador+=1;
numeroClientes(aux->getClienteEsquerda(),contador);
numeroClientes(aux->getClienteDireita(),contador);
}
}
int Arvore::getAltura(Cliente *aux)
{
int altura_e,altura_d=0;
if(aux==NULL)
return 0;
else
{
altura_e=getAltura(aux->getClienteEsquerda());
altura_d=getAltura(aux->getClienteDireita());
if(altura_e>altura_d)
return altura_e+1;
else
return altura_d+1;
}
}
void Arvore::numeroNoFolhas(Cliente *aux,int *cont_folhas)
{
if(aux!=NULL)
{
if((aux->getClienteDireita()==NULL)&&(aux->getClienteEsquerda()==NULL))
*cont_folhas+=1;
numeroNoFolhas(aux->getClienteEsquerda(),cont_folhas);
numeroNoFolhas(aux->getClienteDireita(),cont_folhas);
}
}
void Arvore::percorrePreOrdem(Cliente *aux){
if (aux != 0) {
cout << " " << aux->getChave() << " ";
percorrePreOrdem(aux->getClienteEsquerda());
percorrePreOrdem(aux->getClienteDireita());
}
}
void Arvore::percorreCentral(Cliente *aux){
if (aux != 0) {
percorreCentral(aux->getClienteEsquerda());
cout << " " << aux->getChave() << " ";
percorreCentral(aux->getClienteDireita());
}
}
void Arvore::percorrePosOrdem(Cliente *aux){
if (aux != 0) {
percorrePosOrdem(aux->getClienteEsquerda());
percorrePosOrdem(aux->getClienteDireita());
cout << " " << aux->getChave() << " ";
}
}
int Arvore::getNivelElemento(Cliente *aux,int elemento)
{
int niv =0;
if(aux!=NULL)
{
niv=1;
while(aux!=NULL && aux->getChave()!=elemento)
{
if(elemento<aux->getChave())
aux = aux->getClienteEsquerda();
else
aux = aux->getClienteDireita();
niv+=1;
}
return niv;