Tipos de Árvores

As árvores binárias podem apresentar 4 tipos particulares.
1- Árvore degenerada : é semelhante a uma lista enncadeada pois apresenta apenas um nó por nível.
2- Heap : Nó raiz apresenta valor menor do que os nós filhos.
3- Árvore Completa : Os nós filhos existem somente o penúltimo e último nível da árvore
4- Árvore Cheia : Nós filhos aparecem somente no último nível.


Neste exercício, será criada uma árvore, no qual os valores serão inseridos pelo próprio programador, e o programa irá retornar uma resposta: Se esta árvore é degenerada.


#ifndef _BTREE_H
#define _BTREE_H

#include
#include
#include
#include
using namespace std;

class node; // prototipo da classe node

typedef node *ptrno; // criando um tipo de dados ptrno ponteiro para node

/*
Construcao da classe node.
*/

class node{
private:
int valor;
ptrno esq, dir;
public:
node(){valor=0; esq=dir=NULL;}
node(int v){valor=v; esq=dir=NULL;}
void setValor(int v){valor=v;}
void setEsq(ptrno e){esq=e;}
void setDir(ptrno d){dir=d;}
int getValor(){return valor;}
ptrno getEsq(){return esq;}
ptrno getDir(){return dir;}
};

class btree{
private:
ptrno raiz;
// as chamadas recursivas sao privadas e soh podem ser executadas a partir de metodos do objeto.
void push(ptrno &, int);
void showCentral(ptrno);
void showPreOrdem(ptrno);
void showPosOrdem(ptrno);
void showFolhas(ptrno);
bool isDegenerada(ptrno);
public:
btree(){raiz = NULL;}
ptrno getRaiz(){return raiz;}
// a seguir, as interfaces de funcoes recursivas
void push(int v);
void showCentral();
void showPreOrdem();
void showPosOrdem();
void showFolhas();
void isDegenerada();
};

// interface publica da funcao recursiva push (insere um novo nó na btree)
void btree::push(int v){
push(raiz, v);
}

// rotina push a ser chamada pela interface publica (insere um novo no na subarvore cuja raiz eh r
void btree::push(ptrno &r, int v){
ptrno aux;
if (r!=NULL){ // se o no atual nao for NULL, a insercao deve ser feita em uma das subarvores (esq ou dir)
if (v > r->getValor()){ // v eh maior que o valor do no e deve ser inserido na subarvore direita
aux=r->getDir();
push(aux, v);
r->setDir(aux);
}
else{ // v nao eh maior que o valor do no e deve ser inserido na subarvore esquerda
aux=r->getEsq();
push(aux, v);
r->setEsq(aux);
} // note que o objeto aux eh utilizado para recuperar possiveis alteracoes na subarvore
}
else{ // o trecho seguinte eh executado se no caminhamento pela arvore cairmos em um node NULL (r==NULL),
// o que indica que eh a posicao onde o valor deve ser inserido
aux=new(node); // usando construtor da classe node, valor=0, esq=dir=NULL (vide node())
aux->setValor(v);
r=aux;
}
}

void btree::showCentral(){
showCentral(raiz);
}

void btree::showCentral(ptrno r){ // caminhamento ESQ - RAIZ - DIR
if(r!=NULL){
showCentral(r->getEsq()); // imprime toda a subarvore ESQ com caminhamento central
cout <<>getValor() << " "; // imprime o valor armazenado na raiz showCentral(r->getDir()); // imprime toda a subarvore DIR com caminhamento central
}
}

void btree::showPreOrdem(){
showPreOrdem(raiz);
}

void btree::showPreOrdem(ptrno r){ // caminhamento RAIZ - ESQ - DIR
if(r!=NULL){
cout <<>getValor() << " "; showPreOrdem(r->getEsq());
showPreOrdem(r->getDir());
}
}

void btree::showPosOrdem(){
showPosOrdem(raiz);
}

void btree::showPosOrdem(ptrno r){ // caminhamento ESQ - DIR - RAIZ
if(r!=NULL){
showPosOrdem(r->getEsq());
showPosOrdem(r->getDir());
cout <<>getValor() << " "; } } void btree::showFolhas(){ showFolhas(raiz); } void btree::showFolhas(ptrno r){ // imprime folhas por caminhamento ESQ - RAIZ - DIR if(r!=NULL){ showFolhas(r->getEsq()); // imprime toda as folhas da subarvore ESQ com caminhamento central
if(r->getEsq()==NULL && r->getDir()==NULL) cout <<>getValor() << " "; // imprime o valor armazenado na raiz, se ela for folha showFolhas(r->getDir()); // imprime toda as folhas da subarvore DIR com caminhamento central
}
}
void btree::isDegenerada(){
if(isDegenerada(raiz) == true){
cout << "A arvore eh degenerada!"; } else { cout << "A arvore NAO eh degenerada!"; } } bool btree::isDegenerada(ptrno r){ // caminhamento ESQ - RAIZ - DIR if(r!=NULL){ cout << "Valor " <<>getValor() << " | "; if(r->getEsq() == NULL){
cout << "A esquerda eh NULL | "; } else { cout << "A esquerda NAO eh NULL | "; } if(r->getDir() == NULL){
cout << "A direita eh NULL | "; } else { cout << "A direita NAO eh NULL | "; } if( (r->getEsq() == NULL && r->getDir() != NULL) || (r->getEsq() != NULL && r->getDir() == NULL) ){
cout <<>getEsq() != NULL){
cout <<>getEsq());
} else {
cout <<>getDir());
}
} else if(r->getEsq() == NULL && r->getDir() == NULL){
cout <<>



using namespace std;

int main()
{
btree a1; // criando o objeto a1 da classe btree

// as linhas seguintes estao inserindo valores no objeto b1 usando o metodo push

a1.push(60);
a1.push(30);
a1.push(90);
a1.push(20);
a1.push(40);
a1.push(70);
a1.push(65);
a1.push(85);
a1.push(35);
a1.push(15);
a1.push(115);
a1.push(75);
a1.push(100);
a1.push(25);
a1.push(45);


// a seguir serao impressos na tela os valores armazenados no objeto a1
// usando as tres modalidades de caminhamento.

cout << "Caminhamento Central: ESQ - RAIZ - DIR" << endl; cout << endl;
a1.showCentral(); cout << endl; cout << endl;
cout << "Caminhamento PreOrdem: RAIZ - ESQ - DIR" << endl; cout << endl;
a1.showPreOrdem(); cout << endl; cout << endl;
cout << "Caminhamento PosOrdem: ESQ - DIR - RAIZ" << endl; cout << endl;
a1.showPosOrdem(); cout << endl; cout << endl;
a1.isDegenerada(); cout << endl; cout << endl;
cout << "Imprime Folhas da Arvore" << endl; cout << endl;

a1.showFolhas();

cout << "Programa executado!" << endl;
getch();
return 0;

}