#include <stdio.h>
#include <conio.h>
/**
* Classe de nó binário
*/
class bnode;
typedef bnode *ptrno;
class bnode{
private:
int valor;
ptrno esquerda;
ptrno direita;
public:
bnode(){valor=0;esquerda=direita=NULL;}
void setValor(int v);
void setEsquerda(ptrno n);
void setDireita(ptrno n);
int getValor();
ptrno getEsquerda();
ptrno getDireita();
};
/**
* Define um valor para o nó
*/
void bnode::setValor(int v){
valor = v;
}
/**
* Define o nó a esquerda
*/
void bnode::setEsquerda(ptrno n){
esquerda = n;
}
/**
* Define um nó a direita
*/
void bnode::setDireita(ptrno n){
direita = n;
}
/**
* Retorna o valor do nó
*/
int bnode::getValor(){
return valor;
}
/**
* Retorna o endereço do nó a esquerda
*/
ptrno bnode::getEsquerda(){
return esquerda;
}
/**
* Retorna o endereço do nó a direita
*/
ptrno bnode::getDireita(){
return direita;
}
/**
* Classe de arvore binária
*/
class btree{
private:
ptrno raiz;
void push(ptrno &r, int v);
void mostreCrescente(ptrno r);
void mostreDecrescente(ptrno r);
int maior(ptrno r);
int menor(ptrno r);
int numeroNos(ptrno r);
int altura(ptrno r);
void nosInternos(ptrno r);
int numeroFolhas(ptrno r);
bool isDegenerada(ptrno r);
bool isCompleta(ptrno r, int n,int h);
bool isCheia(ptrno r, int n,int h);
void posOrdem(ptrno r);
void parentAnin(ptrno r);
void hierar2(ptrno r, int h);
bool isEstrBinary(ptrno r);
public:
btree(){raiz = NULL;}
void push(int v);
void mostreCrescente();
void mostreDecrescente();
int maior();
int menor();
int numeroNos();
int altura();
void nosInternos();
int numeroFolhas();
bool isDegenerada();
bool isCompleta();
bool isCheia();
void posOrdem();
void parentAnin();
void hierar2();
bool isEstrBinary();
};
/**
* Interface para o método push
*/
void btree::push(int v){
push(raiz,v);
}
/**
* Insere um valor na btree (menor a esquerda, maior a direita)
*/
void btree::push(ptrno &r, int v){
ptrno aux;
if(r==NULL){
r = new(bnode);
r->setValor(v);
r->setEsquerda(NULL);
r->setDireita(NULL);
}else if(v > r->getValor()){
aux = r->getDireita();
push(aux,v);
r->setDireita(aux);
}else{
aux = r->getEsquerda();
push(aux,v);
r->setEsquerda(aux);
}
}
/**
* Interface para o método mostreCrescente
*/
void btree::mostreCrescente(){
mostreCrescente(raiz);
}
/**
* Método que exibe os valores em ordem crescente (ordem central, esquerda - raiz - direita)
*/
void btree::mostreCrescente(ptrno r){
if(r != NULL){
mostreCrescente(r->getEsquerda());
printf("%d ",r->getValor());
mostreCrescente(r->getDireita());
}
}
/**
* Interface para o método mostreDecrescente
*/
void btree::mostreDecrescente(){
mostreDecrescente(raiz);
}
/**
* Exibe os valores da arvore binaria em ordem decrecente (direita - raiz - esquerda)
*/
void btree::mostreDecrescente(ptrno r){
if(r != NULL){
mostreDecrescente(r->getDireita());
printf("%d ",r->getValor());
mostreDecrescente(r->getEsquerda());
}
}
/**
* Interface para o método maior
*/
int btree::maior(){
return maior(raiz);
}
/**
* Retorna o maior valor na árvore binária (extrema direita)
*/
int btree::maior(ptrno r){
if(r->getDireita() != NULL)
return maior(r->getDireita());
else
return r->getValor();
}
/**
* Interface para o método menor
*/
int btree::menor(){
return menor(raiz);
}
/**
* Retorna o menor valor na árvore binária (extrema esquerda)
*/
int btree::menor(ptrno r){
if(r->getEsquerda() != NULL)
return menor(r->getEsquerda());
else
return r->getValor();
}
/**
* Interface para o método numeroNos
*/
int btree::numeroNos(){
return numeroNos(raiz);
}
/**
* Retorna a quantidade de nós existentes na árvore binária
*/
int btree::numeroNos(ptrno r){
if(r != NULL)
return numeroNos(r->getEsquerda()) + numeroNos(r->getDireita()) +1;
else
return 0;
}
/**
*métodos que serão utilizados nos métodos a seguir
*/
/**
*método max compara dois valores inteiros e retorna o valor maior
*/
int max(int a, int b){
if(a > b)
return a;
else
return b;
}
/**
*método equal compara dois dados do tipo bool e se os dois dados em questão
*forem true, o método retorna true, senão retorna false
*/
bool equal(bool a, bool b){
if(a==true && b==true)
return true;
else
return false;
}
/**
* Interface para o método altura
*/
int btree::altura(){
return altura(raiz);
}
/**
* Retorna a altura da árvore binária
*/
int btree::altura(ptrno r){
if(r != NULL)
return 1+max(altura(r->getEsquerda()),altura(r->getDireita()));
else
return 0;
}
/**
* Interface para o método nosInternos
*/
void btree::nosInternos(){
nosInternos(raiz);
}
/**
* Exibe os valores dos nós internos da árvore binária
*/
void btree::nosInternos(ptrno r){
if(r!=NULL){
nosInternos(r->getEsquerda());
if(r->getEsquerda() == NULL){
if(r->getDireita() != NULL)
printf("%d ", r->getValor());
}else
printf("%d ", r->getValor());
nosInternos(r->getDireita());
}
}
/**
* Interface para o método numeroFolhas
*/
int btree::numeroFolhas(){
return numeroFolhas(raiz);
}
/**
* Retorna a quantidade de nós folha
*/
int btree::numeroFolhas(ptrno r){
if(r!=NULL){
if(r->getEsquerda() == NULL && r->getDireita() == NULL)
return 1;
else
return numeroFolhas(r->getEsquerda())+numeroFolhas(r->getDireita());
}
else
return 0;
}
/**
* Interface para o método isDegenerada
*/
bool btree::isDegenerada(){
return isDegenerada(raiz);
}
/**
* Verifica se a árvore é degenerada e, caso seja, retorna true. Caso não seja degenerada, retorna false
*/
bool btree::isDegenerada(ptrno r){
if(r != NULL){
if(r->getEsquerda() != NULL && r->getDireita() != NULL)
return false;
else if(r->getDireita() == NULL && r->getEsquerda() == NULL)
return true;
else{
//return true;
if(r->getEsquerda() != NULL)
return isDegenerada(r->getEsquerda());
else
return isDegenerada(r->getDireita());
}
}
else
return true;
}
/**
* Interface para o método isCheia
*/
bool btree::isCheia(){
return isCheia(raiz, 1, altura());
}
/**
* Verifica se a árvore é cheia e, caso seja, retorna true
*/
bool btree::isCheia(ptrno r, int n,int h){
if(r != NULL){
if(r->getEsquerda()!=NULL && r->getDireita()!=NULL)
return equal(isCheia(r->getEsquerda(),n+1,h), isCheia(r->getDireita(),n+1,h));
else{
if(n >= h)
return true;
else
return false;
}
}
else
return true;
}
/**
* Interface para o método isCompleta()
*/
bool btree::isCompleta(){
return isCompleta(raiz, 1, altura());
}
/**
* Verifica se a árvore é completa e, caso seja, retorna true
*/
bool btree::isCompleta(ptrno r, int n,int h){
if(r != NULL){
if(r->getEsquerda()!=NULL && r->getDireita()!=NULL)
return equal(isCompleta(r->getEsquerda(),n+1,h), isCompleta(r->getDireita(),n+1,h));
else{
if(n >=(h-1))
return true;
else
return false;
}
}
else
return true;
}
/**
* Interface para o método parentAnin
*/
void btree::parentAnin(){
parentAnin(raiz);
}
/**
* Exibe a árvore como parenteses aninhados
*/
void btree::parentAnin(ptrno r){
if(r!=NULL){
printf("(%d",r->getValor());
parentAnin(r->getEsquerda());
parentAnin(r->getDireita());
printf(")");
}
}
/**
* Interface para o método hierar2
*/
void btree::hierar2(){
hierar2(raiz,1);
}
/**
* Exibe a árvore como Hierarquica 2
*/
void btree::hierar2(ptrno r, int h){
if(r!=NULL){
int i;
printf("%d\n",r->getValor());
if(r->getEsquerda()!=NULL)
for(i=0;i<h;i++)
printf(" ");
hierar2(r->getEsquerda(),h+1);
if(r->getDireita()!=NULL)
for(i=0;i<h;i++)
printf(" ");
hierar2(r->getDireita(),h+1);
}
}
/**
* Interface para o método posOrdem
*/
void btree::posOrdem(){
posOrdem(raiz);
}
/**
* Exibe o conteúdo da árvore em pós ordem (esquerda - direita - raiz)
*/
void btree::posOrdem(ptrno r){
if(r!=NULL){
posOrdem(r->getEsquerda());
posOrdem(r->getDireita());
printf("%d ",r->getValor());
}
}
/**
* Interface para o método isEstrBinary
*/
bool btree::isEstrBinary(){
return isEstrBinary(raiz);
}
/**
* Verifica se a árvore é estritamente binária e retorna true caso seja
*/
bool btree::isEstrBinary(ptrno r){
if(r!=NULL){
if(r->getEsquerda()!=NULL && r->getDireita()!=NULL || r->getEsquerda()==NULL && r->getDireita()==NULL)
return equal(isEstrBinary(r->getEsquerda()),isEstrBinary(r->getDireita()));
else
return false;
}
else
return true;
}
/*Old method, by Sanja
bool btree::isEstrBinary(ptrno r){
if (r != NULL){
if (r->getEsquerda() == NULL && r->getDireita() == NULL)
return true;
if (r->getEsquerda() == NULL && r->getDireita() == NULL || r->getEsquerda() != NULL && r->getDireita() != NULL){
if (isEstrBinary(r->getEsquerda()) == true && isEstrBinary(r->getDireita()) == true)
return true;
else
return false;
}
else
return false;
}
else
return false;
}
*/
int main(){
btree a;
a.push(50);
a.push(30);
a.push(70);
a.push(20);
a.push(40);
a.push(60);
a.push(90);
a.push(35);
a.push(45);
a.push(55);
printf("\nConteudo da arvore em pos-ordem: "); a.posOrdem();
printf("\n\nNumeros de Nos = %d",a.numeroNos());
printf("\nAltura da arvore = %d",a.altura());
printf("\n\nMenor valor = %d", a.menor());
printf("\nMaior valor = %d",a.maior());
printf("\n\nCrescente: ");a.mostreCrescente();
printf("\nDecrescente: ");a.mostreDecrescente();
printf("\n\nNos Internos: ");a.nosInternos();
printf("\nNumero de nos Folha: %d",a.numeroFolhas());
printf("\n\ne uma arvore completa? "); a.isCompleta() ? printf("Sim") : printf
("Nao");
printf("\n\ne uma arvore cheia? "); a.isCheia() ? printf("Sim") : printf("Nao");
printf("\n\ne uma arvore degenerada? "); a.isDegenerada() ? printf("Sim") : printf
("Nao");
printf("\n\ne uma arvore estritamente binaria? "); a.isEstrBinary() ? printf("Sim") : printf("Nao");
printf("\n\nRepresentaçao do conteudo da arvore em parenteses aninhados:\n"); a.parentAnin();
printf("\n\nRepresentaçao do conteudo da arvore em Hierarquico II\n"); a.hierar2();
getch();
return 0;
}
Flickr agora em português. Você clica, todo mundo vê. Saiba mais.
2 comentários:
Valeu por ter colocado que fui eu quem fez um dos metodos ai na sua classe ..hehehe
San Joseph of the Fields
Valeu por ter colocado que foi eu quem fez um dos metodos que está na classe de voces..heheh
San Joseph of the Fields
Postar um comentário