DEGENERADA, CHEIA E COMPLETA

/*
Estou postando os trechos dos 3 exercícios q faltavam
a definição é:
degenerada - um nó por nível, completa - as folhas estão no ultimo e penúltimo nível, cheia - as folhas estão apenas no ultimo nível (eu acho)
*/

//btree.h

class btree{

private:

bool Degenerada(ptrno);
int completa(ptrno, int);
int cheia(ptrno, int);

public:

bool Degenerada();
int completa();
int cheia();

};
//chamada do método degenerada
bool btree:: Degenerada(){
Degenerada (raiz);//passando a raiz como parametro
}

bool btree:: Degenerada(ptrno r){
//verifica se a arvore tem mais de 1 nó por nível
if (r->getEsq()!=NULL && r->getDir()!=NULL)
return false;//se sim retorna falsa
else{
//condição para o ultimo nó
if (r->getEsq()==NULL && r->getDir()==NULL)
return true;
//esse trecho faz o zig-zag da arvore
if (r->getEsq()!=NULL)//vá para a esquerda se o nó ñ for NULL
return Degenerada(r->getEsq());
else
return Degenerada(r->getDir());//caso contrário vá para a direita
}
}
/*inicializa o método passando como parâmetro raiz e zero, qp é o nível de cada nó e será utilizado para a comparação dos nós, se o método retornar ao main zero é porque a arvore está vazia ou não é completa*/
int btree:: completa(){
completa (raiz, 0);
}

int btree:: completa (ptrno r, int qd){
/*quando chegar ao ultimo nó ou a arvore estiver vazia retorna qd*/
if (r==NULL){ return qd;}
else{
/* caso contrário qd incrementa 1, assim a arvore tem 1 ou mais nós*/
qd++;
/*declarei as variáveis "e" (esquerda) e "d"(direita)para melhor entendimento*/
int e = completa(r->getEsq(),qd);
int d = completa(r->getDir(),qd);
/*o trecho abaixo irá retornar sempre o nó mais distante*/
/*se esquerda e direita estejam no mesmo nível ou esquerda esteja 1 nível baixo da direita retorna "e"*/
if (e==d || (e+1)==d){ return e;}
else{
/*caso a direita esteja 1 nível baixo da esquerda retorna "d"
if ((e-1)==d){ return d; }
/*caso a diferença entre os nós seja maior que 1 irá retornar 0*/
else {return 0;
}
}
}
}

int btree:: cheia(){
cheia (raiz, 0);
}
/*método muito parecido com o anterior, também se retornar ao main zero é porque a arvore está vazia ou não é cheia*/
int btree:: cheia (ptrno r, int qd){
if (r==NULL){ return qd;}/*quando chegar ao ultimo nó ou a arvore estiver vazia retorna qd*/
else{
qd++;
int e = cheia(r->getEsq(),qd);
int d = cheia(r->getDir(),qd);
/*caso os nós estejam no mesmo nível retorne "e"*/
if (e==d ){ return e;}
/*caso contrário retorna zero*/
else{return 0; }
}
}

//main

//DEGENERADA
cout << "\n" <<"Teste para ARVORE DEGENERADA:" << endl;
if (a1.Degenerada()== true)
/* Se for true imprime degenerada*/
cout << "\n" << "E' Degenerada" << endl;
else
/*se não imprime não é degenerada*/
cout << "\n" << "Nao e' Degenerada" << endl;

//CHEIA
cout << "\n" <<"Teste para ARVORE CHEIA:" << endl;
if ((a1.cheia())== 0)//se for zero a arvore ñ é cheia
cout << "\n" << "Nao e' cheia" << endl;
else
cout << "\n" << "E' cheia" << endl;

//COMPLETA
cout << "\n" <<"Teste para ARVORE COMPLETA:" << endl;
if ((a1.completa())== 0)//se for zero a arvore ñ é completa
cout << "\n" << "Nao e' completa" << endl;
else
cout << "\n" << "E' completa" << endl;