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;

}

Criando a Classe Árvore

A partir da Classe Principal da Postagem anterior vamos criar a Classe da Árvore
Binária e a partir dela realizar algumas tarefas:

class btree{ //Esta é a classe da árvore binária
private:
ptrno raiz;
public:
btree () {raiz=NULL;}

void push (int); //Neste ponto começa a ser declarada as funções que irão
void push (ptrno &r, int v); // realizar as tarefas.
int maior();
int maior(ptrno r);
int menor();
int menor (ptrno r);
int size ();
int size(ptrno r);
int a();
int a(ptrno h);
void impinternos ();
int impinternos(ptrno r);
};

//Acima estão apenas as chamadas de cada função. O que cada uma realmente deve fazer segue abaixo:

// A função push irá adicionar valores para a árvore, lembrando que neste caso os valores serão colocados em ordem crescente.

void btree::push (int v){
push (raiz,v);
}

void btree::push (ptrno &r, int v)
{
ptrno aux;
if (r==NULL)
{
r = new (node);
r->setValor (v);
r->setEsq(NULL);
r->setDir(NULL);
}
else
if (v>r->getValor())
{
aux = r->getDir();
push (aux, v);
r->setDir(aux);
}
else aux=r->getEsq();
push (aux, v);
r->setEsq(aux);
}

/* A função maior irá retornar o maio valor que a árvore possuir. Aqui ela foi resolvida de duas maneiras: uma usando recursidade(o problema maior dividido em problemas menores com as mesmas características), e usando interatividade (da maneira básica).
*/

int btree::maior() {
return maior (raiz);
}

int btree::maior (ptrno r){ //RECURSIVIDADE
if (r==NULL)
return 0;
if (r->getDir()== NULL)
return r->getValor();
else
return maior (r->getDir());
}

/* int btree::maior(){ //INTERATIVIDADE
ptrno aux= raiz;
if (aux==NULL)
return 0;
while (aux->getdir()!=NULL)
aux=aux->getdir();
return aux->getvalor();
}
*/

// Função menor irá retornar o menor valor da árvore
int btree::menor() {
return menor (raiz);
}
int btree::menor (ptrno r){
if (r==NULL)
return 0;
if (r->getDir()== NULL)
return r->getValor();
else
return menor (r->getDir());
}

// Função size retorna a quantidade de valores armazenados na árvore
int btree:: size (){
return size(raiz);
}

int btree::size(ptrno r){
if (r!=NULL)
return 1 + size (r->getEsq()) + size(r->getDir());
else
return 0;
}

// a função a retorna a altura da árvore binária
int btree:: a(){
return a(raiz);
}


int btree::a(ptrno r){
if (r!=NULL)
return 1 + max (a(r->getEsq()), a(r->getEsq()));
else
return 0;
}

int max (int a, int b){
if (a > b)
return a;
else
return b;
}

// a função impinternos imprime os valores dos nós internos
void btree::impinternos (){
impinternos(raiz);}

int btree::impinternos(ptrno r){
if (r!=NULL)
if (r->getEsq()!=NULL || r->getDir()!=NULL)
cout <<>getValor() <getEsq());
impinternos (r->getDir());
}

Abaixo segue a função main do código:

int main()
{
btree arvore;

arvore.push(); //Lembrando que dentro dos parênteses devem ser colocados os
arvore.maior(); //valores que serão armazenados na árvore.
arvore.menor();
arvore.size ();
arvore.a();
arvore.impinternos ();

getch();
}

Árvore Binária - Classe Principal

Definições de árvore binária
Árvore, no contexto da programação e da ciência da computação é uma estrutura de dados que herda as características das topologias em árvore. Conceptualmente diferente das listas encadeadas, em que os dados se encontram numa sequência, nas árvores os dados estão dispostos de forma hierárquica.

A árvore é composta por um elemento principal chamado raiz, que possui ligações para outros elementos, que são denominados de galhos ou filhos. Estes galhos levam a outros elementos que também possuem outros galhos. O elemento que não possui galhos é conhecido como folha ou nó terminal.

O número máximo de galhos em um elemento é chamado ordem da árvore. Uma árvore binária é aquela de ordem 2, em que cada elemento possui no máximo 2 galhos.

O primeiro exercício a ser publicado é a Classe Principal de uma Árvore Binária.

#include
#include
#include

class node;

typedef node *ptrno;

class node {
private:
int valor;
ptrno esq, dir;

public:
node() {valor = 0 , 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; }

};

Breve explicação:

Esse é o metodo construtor da classe nó.

Como parâmetros privados temos valor e os ponteiros que irão armazenar os valores da esquerda e direita.

Depois como parâmetros públicos temos os valores inicias, as atribuições para os valores para V e para esq e dir de cada paramentro criado, e as funções set para substituir os parâmetros privados, pois não podemos acessá-los diretamente.

Então, com a função GET o programa retornará os valores atribuídos.

No programa principal escreve-se o valor de V e fica um ponteiro guardando o endereço de memória de esq e dir.