arvoreBinariaTex

Prévia do material em texto

Implementacao da arvore binaria
Denis R. S. Pinheiro
September 28, 2013
#inc lude <s t d i o . h>
#inc lude <s t d l i b . h>
s t r u c t no
{
i n t va l o r ;
s t r u c t no ∗ esq ;
s t r u c t no ∗ d i r ;
} ;
typede f s t r u c t no No ;
// recebe r a i z ( i n i c i o da arvore ) e um novo n
//quando eu quero a l t e r a r o ponte i r o do i n i c i o , recebo uma r e f e r e n c i a para o ponte i r o (∗∗ )
No∗ cr iarNo ( i n t v ){
No∗ novo = (No∗) mal loc ( s i z e o f (No ) ) ;
novo−>va lo r = v ;
novo−>esq = NULL;
novo−>d i r = NULL;
re turn novo ;
}
void i n s e r i r (No ∗∗ r , i n t v )
{
No∗ novo = cr iarNo (v ) ;
i f (∗ r == NULL)
1
{
∗ r = novo ;
// p r i n t f (”∗∗Valor %d i n s e r i d o na r a i z .∗∗\n” , novo−>va lo r ) ;
} e l s e {
No∗ a = ∗ r ; // c r i a nova va r i a v e l para guardar ponte i r o para i n i c i o
No∗ b ;
whi l e ( a!=NULL){
b=a ;
i f ( a−>va lo r > novo−>va lo r )
{
a=a−>esq ;
} e l s e {
a=a−>d i r ;
}
}
i f (b−>va lo r > novo−>va lo r )
{
b−>esq = novo ;
// p r i n t f (”∗∗Valor %d i n s e r i d o na esquerda .∗∗\n” , novo−>va lo r ) ;
} e l s e {
b−>d i r = novo ;
// p r i n t f (”∗∗Valor %d i n s e r i d o na d i r e i t a .∗∗\n” , novo−>va lo r ) ;
}
}
}
No∗ busca (No∗ r , i n t k ){
// p r i n t f (” Prcurando va l o r −%d−\n\n” , k ) ;
whi l e ( r != NULL){
i f ( k > r−>va lo r ){
r = r−>d i r ;
} e l s e {
i f ( k < r−>va lo r ){
r = r−>esq ;
} e l s e {
r e turn r ;
}
}
2
}
// p r i n t f (” Valor n o encontrado . . . \ n ” ) ;
r e turn NULL;
}
void imprimir (No ∗ r ){
i f ( r != NULL){
imprimir ( r−>esq ) ;
p r i n t f (”%d\n” , r−>va lo r ) ;
imprimir ( r−>d i r ) ;
}
}
No∗ c r i a ( void ){
No ∗ r = NULL;
re turn r ;
}
void l i b e r a (No ∗ l ){
i f ( l != NULL){
l i b e r a ( l−>esq ) ;
l i b e r a ( l−>d i r ) ;
f r e e ( l ) ;
}
}
i n t main ( )
{
No∗ r = cr iaArvore ( ) ;
No∗ novo ;
srand ( time (NULL) ) ;
i n t i ;
f o r ( i =1; i <10; i++)
{
i n s e r i r (&r , rand ()%20) ;
p r i n t f (”\n ” ) ;
3
}
No∗ r e sSearch ;
r e sSearch = busca ( r , rand ()%20) ;
i f ( r e sSearch !=NULL)
{
p r i n t f (” Valor encontrado : %d\n\n” , resSearch−>va lo r ) ;
} e l s e {
p r i n t f (”Warning : Valor nao encontrado\n ” ) ;
}
r e turn 0 ;
}
/∗
∗ By : Denis P inhe i ro . Todos os d i r e i t o s r e s e rvados .
∗ 17 :05 :2013
∗/
4