Exercícios de Grafos III

O método a seguir irá ler uma matriz de Incidência e armazenar o grafo em uma Lista de Adjacência:

void matrizIncidencia(){
int x, y;

for ( int i = 1; i<= no; i++){
for ( int j = 1; i<=aresta ; j++){
if(matriz[j][i]!=0){
if(x!=0)
y=matriz[j][i];
else
x=matriz[j][i];
}
}
lista->setAresta(x, y, 1, 1 );
}
}

Exercícios sobre Grafos II

O exercício a seguir, irá ler uma matriz de incidência e armazenar o grafo e uma matriz de Adjacência.

Lembrando que este também necessita do arquivo txt que segue abaixo:


1

4

4
3
2
1

4

0 1 A 0
2 0 B 1
3 1 C 0
2 3 D 0

indice do nó para impressão
Qtde nos
nos
.
.
.
qtde arestas
n1 n2 aresta direção



Código:


using namespace std;
class node; // classe NODE
typedef node *ptrno;

class node;

typedef node *ptrno;

class node
{
private:
int vertice,peso;
ptrno prox;
public:
node(){
peso=0;vertice=0; prox=NULL;
}
void setPeso(int p){
peso=p;
}
void setVertice(int v){
vertice=v;
}
void setProx(node *p){
prox=p;
}
node *getProx(){
return prox;
}
};


class Grafo{
private:
int qtdnos;
int **matriz;
ptrno lista;
int *pesos;
public:
Grafo(){
qtdnos=0;
pesos=NULL;
matriz=NULL;
};

void lerArquivoIncidencia(int indice);
};


void Grafo::lerArquivoIncidencia(int indice){
int tamanho,n1,n2,aresta,direcao,qtdaresta,gambiarra;

cin>>tamanho; //le a qtd de NO do grafo
cin>>numerodono >>numerodono >>numerodono >>numerodono ;
cin>>qtdaresta;

matriz = new int*[qtdaresta]; //criacao do vetor q representa
colunas
for(int i = 0; i < tamanho; i++){
matriz[i] = new int[tamanho];
}


for(int k = 0; k < qtdaresta; k++){
for(int l = 0; l < tamanho; l++){
matriz[k][l] = 0;
}
}


for (int n=0;n < qtdaresta;n++){
cin>>n1;
cin>>n2;
cin>>aresta;
cin>>direcao;
matriz[n1][aresta]=1;
matriz[n2][aresta]=1;
}

for (int o=0;o < tamanho;o++){
for (int p=0;p < qtdaresta;p++){
cout << matriz[o][p]<< " ";
}
cout<< endl;
}
cout<< endl;
cout<< "O no " << indice << " tem os seguintes nos adjacentes: " << endl;


for(int r=0;r < qtdaresta;r++){
if(matriz[indice][r]==1){
for(int s=0;s < tamanho;s++){

if(( matriz[s][r]==1)&&(s!=indice))
cout << s <<" ";
}
}
}
}

int main(){
Grafo grafo1;
grafo1.lerArquivoIncidencia(1);
getchar();
}

Exercícios sobre Grafos

Temos aqui 3 exercícios resolvidos no mesmo código. As propostas são:

- Criar um metodo que verifique se o grafo é dirigido

- Construir um método que construa um grafo em Lista de Adjacência

- Construir um metodo que apartir de um grafo armazenado em uma lista
de adjacencia, apresente o grafo na tela na forma de matriz de
adjacencia

*** O programa a seguir precisa do arquivo txt. O arquivo segue abaixo: ***

8


0 8
1 7
2 6
3 5
4 4
5 3
6 2
7 1



7



0 2 1 0
2 3 3 0
3 7 5 0
5 7 2 0
6 7 9 0
2 5 4 0
3 7 6 0



LEGENDA:

QtdNos

NroNo/Valor

QtdArestas

No1/No2/Peso/Direcionado




Código:

class NoGrafo{
private:
int No, Peso, noEhDirigido;
NoGrafo *Aresta;
bool Dirigido;

public:
NoGrafo(){
Aresta = NULL;
No = 0;
noEhDirigido = 0;
Dirigido = false;
}

NoGrafo(int numero, int peso){
Aresta = NULL;
No = numero;
Peso = peso;
}

void setNo(int numero){
No = numero;
}

int getNo(){
return No;
}

void setPeso(int peso){
Peso = peso;
}

int getPeso(){
return Peso;
}

void setNoEhDirigido(int dirigido){
noEhDirigido = dirigido;
}

int getNoEhDirigido(){
return noEhDirigido;
}

void setAresta(NoGrafo *no){

NoGrafo *aux = getAresta();
if(aux == NULL){
Aresta = new NoGrafo(no->getNo(), no->getPeso());
}

else {
while(aux->getAresta() != NULL){
aux = aux->getAresta();
}

aux->Aresta = new NoGrafo(no->getNo(), no->getPeso());
}
}

NoGrafo *getAresta(){
return Aresta;
}

void imprimirAresta(){
NoGrafo *aux;
NoGrafo *aux2;
aux = getAresta();
if(aux != NULL){
while(aux != NULL){
cout << "-> [" << aux->getNo() << "] ";
aux = aux->getAresta();
}
}
cout << "-+";
}
};


class ListaGrafo{
private:
int qtdNos, qtdArestas;
NoGrafo *listaNosPrincipais;
bool ehDirigido;

public:
ListaGrafo(){
qtdNos = 0;
qtdArestas = 0;
ehDirigido = false;
}

void setQtdNos(int qtd){
qtdNos = qtd;
}

int getQtdNos(){
return qtdNos;
}

void setqtdArestas(int qtd){
qtdArestas = qtd;
}

int getqtdArestas(){
return qtdArestas;
}

void lerDadosDoArquivo(){
int qN;
int peso, numero;
int qtdArestas;
char Legenda;

cin >> qN;
cout << "\nEste grafo contem " << qN << " nos." << endl;
cout << "\nQue sao:"<< endl;
cout << "\nNoh\tPeso"<< endl;
setQtdNos(qN);
listaNosPrincipais = new NoGrafo[qN];

for(int i=0;i < getQtdNos(); i++){
cin >> numero;
cin >> peso;
listaNosPrincipais[numero].setNo(numero);
listaNosPrincipais[numero].setPeso(peso);
cout << "" << listaNosPrincipais[numero].getNo() << " \t"
<< listaNosPrincipais[numero].getPeso() << endl;
}
cin >> qtdArestas;
setqtdArestas(qtdArestas);
cout << "\nPossui " << getqtdArestas() << " arestas."<< endl;
cout << "\n" << endl;
for(int i=0; i < getqtdArestas(); i++){
int n1 = 0, n2 = 0, p = 0, d = 0;

cin >> n1;
cin >> n2;
cin >> p;
cin >> d;

listaNosPrincipais[n1].setAresta(new NoGrafo(n2, p));

if(d == 1){
ehDirigido = true;
listaNosPrincipais[n2].setAresta(new NoGrafo(n1, p));

listaNosPrincipais[n1].setNoEhDirigido(1);
listaNosPrincipais[n2].setNoEhDirigido(1);
}
}
}

void imprimirGrafoCompleto(){
cout << " LISTA DE ADJACENCIA" << endl;
cout << "\n" << endl;
for(int i = 0; i < getQtdNos(); i++){

cout << " [" << listaNosPrincipais[i].getNo() << "] ";
listaNosPrincipais[i].imprimirAresta();
cout << endl;
}
}

void isDirigido(){
if(ehDirigido == true){
cout <<"\n\t\t\t_________________________" << endl;
cout << "\n\t\t\tEste grafo EH DIRIGIDO!" << endl;
cout <<"\t\t\t_________________________" << endl;
}
else {
cout <<"\n\t\t\t____________________________" << endl;
cout << "\n\t\t\tEste grafo NAO EH DIRIGIDO! " << endl;
cout <<"\t\t\t____________________________" << endl;
}
}

void imprimirMatrizNaTela(){
NoGrafo *aux = NULL;
cout << "\n\n MATRIZ DE ADJACENCIA"<< endl;
cout << endl;
cout << " ";

for(int x = 0; x < getQtdNos(); x++){
cout << listaNosPrincipais[x].getNo() << " ";
}

cout << endl;

for(int x = 0; x < getQtdNos(); x++){

cout << listaNosPrincipais[x].getNo() << " ";

for(int i = 0; i < getQtdNos(); i++){
cout << " " <<
localizarNo(listaNosPrincipais[x].getAresta(), listaNosPrincipais[i].getNo()) << " ";
}

cout << endl;
}
}

int localizarNo(NoGrafo *primeiro, int indiceABuscar){
NoGrafo *aux = primeiro;
bool encontrou = false;
while(aux != NULL){
if(aux->getNo() == indiceABuscar){
encontrou = true;
break;
}
aux = aux->getAresta();
}

if(encontrou == true){
return 1;
}
else {
return 0;
}
}

};

int main(){
ListaGrafo *meuGrafo = new ListaGrafo();
meuGrafo->lerDadosDoArquivo();
meuGrafo->imprimirGrafoCompleto();
meuGrafo->isDirigido();
cout << endl;
meuGrafo->imprimirMatrizNaTela();
return 0;

}

Proposta:

Definir a classe Grafos composta numa matriz adjacente.

class grafo {

int qtde; //QTD de nós
int *v; //Vetor peso
int **m; //Matriz de Adjacencia
int i,j;

public:

void madj(){
qtde=0;
v=NULL;
m=NULL;
}
void madj(int tam){
qtde=tam;
v= new(int[tam]);
*m=new(int[tam);

for(i=0;i< i="0;i<" j="0;j<">

MATRIZ DE ADJACÊNCIA

A matriz de adjacência é uma matriz de N x N (onde N é o número de vértices do grafo).

Ela inicialmente é preenchida toda com 0 e quando há uma relação entre o vértice do x (número da coluna)
com o do y (número da linha), matriz[x][y] é marcado um 1.


A matriz de adjacência mostra o relacionamento entre os nós de um grafo.

Se um nó a for adjacente a um nó b, então na matriz de adjacência M as entradas M[a,b]
e M[b,a] serão diferentes de 0.

O valor armazenado nestas entradas indicarão a quantidade de arestas existentes entre os vértices a e b.

Matriz Adjacente:

GRAFOS

O artigo de Leonhard Euler, publicado em 1736, sobre o problema das Sete Pontes de Königsberg, é considerado o primeiro resultado da teoria dos grafos. É também considerado um dos primeiros resultados topológicos na geometria; isto é, não dependente de quaisquer medidas. Isso ilustra a profunda conexão entre a teoria dos grafos e topologia.

Ponte de Konigsberg e a sua Representação Gráfica feita por Euler.

Um grafo é um conjunto de pontos, chamados vértices (ou nodos ou nós), conectados por linhas, chamadas de arestas (ou arcos).

Um grafo com 6 vértices e 7 arestas.

Dependendo da aplicação, arestas podem ou não ter direção, pode ser permitido ou não arestas ligarem um vértice a ele próprio. Se as arestas têm uma direção associada (indicada por uma seta na representação gráfica) temos um grafo direcionado, ou dígrafo.

Nós = { A, B, C, D, E, F, G, H }
Arcos: E = {(A,A), (A,B), (A,C), (A,D), (C,D), (C,F), (E,G)}

Um grafo com um único vértice e sem arestas é conhecido como o grafo trivial ou "o ponto".

Conceitos básicos de Teoria dos Grafos

Um laço (loop) num grafo ou num digrafo é uma aresta e em E cujas terminações estão no mesmo vértice. Um digrafo ou grafo é chamado simples se não tem laços e existe no máximo uma aresta entre quaisquer dois vértices.

Exemplo de Grafo

O grafo acima é um grafo simples com o conjunto de vértices V = {1, 2, 3, 4, 5, 6} e um conjunto de arestas E = {(1,2), (1,5), (2,3), (2,5), (3,4), (4,5), (4,6)}.

Uma aresta conecta dois vértices; esses dois vértices são ditos como incidentes à aresta.

A valência (ou grau) de um vértice é o número de arestas incidentes a ele, com loops contados duas vezes. No grafo de exemplo os vértices 1 e 3 possuem uma valência de 2, os vértices 2, 4 e 5 têm a valência de 3 e o vértice 6 tem a valência de 1. Se E é finito, então a valência total dos vértices é o dobro do número de arestas.

Em um dígrafo, distingue-se o grau de saída (o número de arestas saindo de um vértice) e o grau de entrada (o número de arestas entrando em um vértice). O grau de um vértice é igual à soma dos graus de saída e de entrada.

Dois vértices são considerados adjacentes se uma aresta existe entre eles. No grafo acima, os vértices 1 e 2 são adjascentes, mas os vértices 2 e 4 não são. O conjunto de vizinhos de um vértice consiste de todos os vértices adjascentes a ele. No grafo-exemplo, o vértice 1 possui 2 vizinhos: vértice 2 e vértice 5. Para um grafo simples, o número de vizinhos de um vértice é igual à sua valência.

Na computação, um grafo finito direcionado ou não-direcionado (com, digamos, n vértices) é geralmente representado por sua matriz de adjacência: uma matriz n-por-n cujo valor na linha i e coluna j fornece o número de arestas do i-ésimo ao j-ésimo vértices.

Um caminho é uma sequência de vértices tal que de cada um dos vértices existe uma aresta para o vértice seguinte. Um caminho é chamado simples se nenhum dos vértices no caminho se repete. O comprimento do caminho é o número de arestas que o caminho usa, contando-se arestas múltiplas múltiplas vezes. O custo de um caminho num grafo balanceado é a soma dos custos das arestas atravessadas. Dois caminhos são independentes se não tiverem nenhum vértice em comum, excepto o primeiro e o último.

No grafo de exemplo, (1, 2, 5, 1, 2, 3) é um caminho com comprimento 5, e (5, 2, 1) é um caminho simples de comprimento 2.

Se for possível estabelecer um caminho de qualquer vértice para qualquer outro vértice de um grafo, diz-se que o grafo é conexo. Se for sempre possível estabelecer um caminho de qualquer vértice para qualquer outro vértice mesmo depois de remover k-1 vértices, então diz-se que o grafo está k-conexo. Note que um grafo está k-conexo se, e somente se, contém k caminhos independentes entre qualquer par de vértices. O grafo de exemplo acima é conexo (e portanto 1-conexo), mas não é 2-conexo.

Um ciclo (ou circuito) é um caminho que começa e acaba com o mesmo vértice. Ciclos de comprimento 1 são laços. No grafo de exemplo, (1, 2, 3, 4, 5, 2, 1) é um ciclo de comprimento 6. Um ciclo simples é um ciclo que tem um comprimento pelo menos de 3 e no qual o vértice inicial só aparece mais uma vez, como vértice final, e os outros vértices aparecem só uma vez. No grafo acima, (1, 5, 2, 1) é um ciclo simples. Um grafo chama-se acíclico se não contém ciclos simples.

Uma árvore é um grafo simples acíclico e conexo. Às vezes, um vértice da árvore é distinto e chamado de raiz.

Um subgrafo de um grafo G é um grafo cujo conjunto dos vértices é um subconjunto do conjunto de vértices G, cujo conjunto de arestas é um subconjunto do conjunto de arestas de G, e cuja função w é uma restrição da função de G.

Um grafo parcial de um grafo G é um subgrafo com o mesmo conjunto de vértices que G. Uma árvore parcial é um grafo parcial que é árvore. Todo grafo tem pelo menos uma árvore parcial.

O grafo nulo é o grafo cujos conjuntos de vértices e de arestas são vazios.

Um conjunto independente em um grafo é um conjunto de vértices não adjacentes entre si. No exemplo acima, os vértices 1, 3 e 6 formam um conjunto independente e 3, 5 e 6 são outro conjunto independente.

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.