Arvore Bin Exemplo

7/24/2019 Arvore Bin Exemplo

1/22

Estrutura de Dados

rvore Binria

Exemplo de Implementao

Prof. Pedro Lus Antonelli

Anhanguera Educacional


2/22

Lista Encadeada - Exemplo

Exemplo de cdigo para a implementao de uma rvore binria encadeada

emC, para armazenarvalores inteiros, utilizado o compilador GNU g++

#include

typedef struct arvore

{

char info;

struct arvore *esq;

struct arvore *dir;

} Arv;


3/22

Funes de criao e teste

Arv* inicializa( void ) // funo que inicializa uma rvore

{

return NULL;

}

//------------------------------------------------------------------------

int vazia( Arv* a ) // funo que testa se a rvore est vazia

{return a==NULL;

}


4/22

Funo que cria um rvore

Arv* cria(char c, Arv* sub_arv_e, Arv* sub_arv_d )

{

Arv* p = ( Arv* )malloc( sizeof( Arv ) );

p->info = c;

p->esq = sub_arv_e;

p->dir = sub_arv_d;

return p;}


5/22

Funo que imprime a rvore

void imprime ( Arv* a )

{

if (!vazia( a ) )

{

printf(" %c ", a->info); // mostra raiz

imprime(a->esq); // mostra sae

imprime(a->dir); // mostra sad

}}


6/22

Funo que libera a memria alocada para a rvore

Arv* libera ( Arv* a )

{

if (!vazia( a ) )

{

libera(a->esq); // libera saelibera(a->dir); // libera sad

free(a); // libera raiz

}

return NULL;

}


7/22

Funo que retorna a altura de uma rvore

int altura (Arv* a)

{

if ( vazia( a ) ) { return -1; }

else {

if (altura ( a->esq ) > altura ( a->dir ) ) { return 1 + altura ( a->esq ); }

else {

return 1 + altura ( a->dir );

}}

}


8/22

Funo que procura um elemento em uma rvore

int busca (Arv* a, char c){

if (vazia(a))

return 0; // rvore vazia: no encontrou

else

return a->info==c || busca(a->esq,c) || busca(a->dir,c);

}


9/22

Teste das funes criadas

int main( )

{

Arv* no_1= cria(D',inicializa() ,inicializa() ); // sub-rvore D'


10/22


Arv* no_1= cria(D',inicializa() ,inicializa() ); // sub-rvore comD'

Arv* no_2= cria(B',inicializa(), no_1 ); // sub-rvore comB'


11/22


Arv* no_1= cria(D',inicializa() ,inicializa() ); //sub-rvore com 'D'

Arv* no_2= cria(B',inicializa(), no_1 ); // sub-rvore com 'B'Arv* no_3=cria(E',inicializa(), inicializa() ); // sub-rvore com 'E'


12/22


Arv* no_1= cria(D',inicializa() ,inicializa() ); //sub-rvore comD'

Arv* no_2= cria(B',inicializa(), no_1 ); // sub-rvore comB'Arv* no_3=cria(E',inicializa(), inicializa() ); // sub-rvore comE'

Arv* no_4=cria(F',inicializa(), inicializa() ); // sub-rvore comF'


13/22




Arv* no_3=cria(E',inicializa(), inicializa() ); // sub-rvore comE'

Arv* no_4=cria(F',inicializa(), inicializa() ); // sub-rvore comF'

Arv* no_5=cria(C,no_3, no_4); // sub-rvore comC'


14/22



Arv* no_3=cria(E',inicializa(), inicializa() ); // sub-rvore comE'

Arv* no_4=cria(F',inicializa(), inicializa() ); // sub-rvore comF'Arv* no_5=cria(C,no_3, no_4); // sub-rvore comC'

Arv* arvore =cria(A',no_2, no_5 ); // rvore com raizA'


15/22

printf("Arvore antes do acrescimo dos nos: x, y, z \n \n");

imprime(arvore);

printf("\n \n altura da arvore = %d \n \n ",altura(arvore));


16/22

arvore->esq->esq = cria('x',

cria('y',inicializa(),inicializa()),cria('z',inicializa(),inicializa()) );

printf("\n \n Arvore apos o acrescimo dos nos: x, y, z \n \n");

imprime(arvore);

printf("\n \n altura da arvore = %d \n \n ",altura(arvore));


17/22

arvore->dir->esq = libera( arvore->dir->esq );

printf("\n \n Arvore apos a retirada do no: e \n \n ");

imprime(arvore);

printf("\n \n altura da arvore = %d \n \n ",altura( arvore ) );


18/22

char elemento;

printf("Digite o elemento a ser procurado: ");

scanf("%c",&elemento);

if( busca(arvore, elemento) != 0 )

{

printf("\n Elemento encontrado! " );

}

else

{printf("\n Elemento no encontrado! " );

}


19/22

libera(arvore);

system("PAUSE");

return EXIT_SUCCESS;

}


20/22

Exerccios:

1- Modificar o cdigo apresentado para que o mesmo construa uma

rvore binria completa de altura 3;

2- Implementar as funes para imprimir essa rvore das quatromaneiras vistas em aula ( ordem, pr-ordem, ps-ordem e em nvel ).

Envia para o [email protected] at 24/11/2015
mailto:[email protected]:[email protected]:[email protected]


21/22

BIBLIOGRAFIA

W. Celes, W. R. Cerqueira, J.L. Rangel. Introduo a Estruturas de Dados -

com tcnicas de programao em CEd. Campus

TENENBAUM, Aaron M. Estrutura de Dados Usando C. 1 ed. So Paulo:PEARSON EDUCATION, 2005.

VELOSO, Paulo A. S.. Estrutura de Dados. 1 ed. Rio de Janeiro: Campus,1996.

PEREIRA, Silvio do Lago. Estrutura De Dados Fundamentais : ConceitosE Aplicaes. 12 ed. SoPaulo: rica, 2008


22/22

MANZANO, Jos Augusto N. Garcia. Algoritmos : Lgica paradesenvolvimento de programao de computadores. 21 ed.So Paulo:

rica, 2008.

FORBELLONE, A. L.. Lgica De Programao. 1 ed. So Paulo: Pearson,2008.

CORMEN, Thomas H.. Algoritmos : Teoria e Prtica. 2 ed. Rio de Janeiro:Campus, 2002.

http://www.jacintomendes.eti.br/mackenzie/peii/aulas/sandra/PEII_Aula12.pdf. Acesso em 02/02/2012

http://www.dainf.ct.utfpr.edu.br/~karla/Acesso em 02/02/2012

http://www.rcosta62br.unifei.edu.brAcesso em 03/02/2012

http://gaveta-virtual.blogspot.com.br/2011/06/filas.htmlAcesso em 10/04/2012
http://www.jacintomendes.eti.br/mackenzie/peii/aulas/http://www.dainf.ct.utfpr.edu.br/~karla/http://www.rcosta62br.unifei.edu.br_ccf120_aula_2%29acesso/http://gaveta-virtual.blogspot.com.br/2011/06/filas.htmlhttp://gaveta-virtual.blogspot.com.br/2011/06/filas.htmlhttp://gaveta-virtual.blogspot.com.br/2011/06/filas.htmlhttp://www.rcosta62br.unifei.edu.br_ccf120_aula_2%29acesso/http://www.dainf.ct.utfpr.edu.br/~karla/http://www.jacintomendes.eti.br/mackenzie/peii/aulas/

Documents

Arvore Bin Exemplo