Problema com Árvores Binárias - Retornar quantidade de nós

26 de novembro de 2010 6 respostas

Japaf 26 de novembro de 2010

Olá a todos,

Estou estudando árvores binárias e recursividade. Consegui retornar a quantidade de nós da árvore mas agora o exercícios pede para retornar apenas a quantidade de nós folha. Eu tentei inverter o algoritmo que fiz, mas não funcionou.

Por isso vim aqui pedir uma ajuda, por favor.

Colocarei apenas o código do método abaixo para não ficar muito grande.

public int folhasqnt(){
                   int d=0;
                   int e=0;
                   
                  if(esq == null)
                    e = esq.folhasqnt();
                  else
                    e = 0;
                    
                  if(dir == null)
                    d = dir.folhasqnt();
                  else
                    d = 0;
                    
                  return 1+e+d;
}

Executando esse código retorna apenas 1.

Quando fiz para retornar a quantidade geral de nós só mudava o if para

if(esq != null)

Mas para retornar os nós folhas não funciona.

Obrigado pela ajuda

6 Respostas

santanna106 26 de nov. de 2010

vc pode postar o código que vc usa para percorrer a árvore?

não entendi como vc está fazendo essa busca.

Japaf 26 de nov. de 2010

Certo, vou postar todo o código aqui.

Classe Principal:

public class Principal
{
    public static void main(String args[]){
        Btree a = new Btree();
        
        a.push(50);  
        a.push(30);
        a.push(10);
        a.push(20);
        a.push(90);
        a.push(100);
        a.push(70);
    
       a.show();   
    
       System.out.println(a.folhasqnt());
       
     }
   }

Classe Btree:

public class Btree
{
    private Bnode raiz;
    
    public Btree(){  //método construtor
        raiz=null;
    }
    
    public void push(int v){
       if(raiz==null)    //comparação raiz = 0
         raiz=new Bnode(v);  //criar raiz
       else
         raiz.push(v);  //iniciar com valor
  
        }
        
         public void show(){
                if(raiz!=null)
                   raiz.show();  //mostrar valor
                }              

             
             public int folhasqnt(){
                 if(raiz!=null)
                 return raiz.folhasqnt();
                 else
                   return 0;
                }
             
            
            
          }

Classe Bnode:

public class Bnode
{
       private int valor;   //váriavel para valor
       private Bnode esq,dir;  //váriavel para direito e esquerdo
            
        public Bnode(int v){
                valor=v;   //valor=v
                esq=null;   //inicio do valor = 0
                dir=null;
            }
            
            //prestar atenção NO VALOR 
            // valor maior que a raiz vai para direita
            //valor menor que a raiz vai para a esquerda
            
         public void push(int v){
             if(valor>=v){   //colocar o valor a esquerda
                 if(esq==null){
                 esq= new Bnode (v);  //criar novo valor
                }
                 else
                    {
                    esq.push(v); //colocar o valor na esquerda
                }
            }
             else
             {
                if(dir==null){   //comparação
                dir= new Bnode(v);  //criar novo valor
            }
            
             else { 
                   dir.push(v);  //colocar o valor na direita
                }
            }
        }
              
                      
            public void show(){
                System.out.println(valor); //imprimir valor
                
                if(esq!=null){
                   esq.show();  
                }
                   
                if(dir!=null){
                   dir.show();  
                }
            }
            

            public int folhasqnt(){
                   int d=0;
                   int e=0;
                   if(esq==null)
                        e = esq.folhasqnt();
                   else
                        e=0;
                   if(dir==null)     
                        d = dir.folhasqnt();
                   else
                        d = 0;
                        
                  return 1+e+d;   
                }
        }

Segue todo o código.
Obrigado pelo interesse em ajudar.

santanna106 26 de nov. de 2010

Cara,

exite um erro conceitual na inclusão dos elementos da sua árvore binária.

Em uma árvore binária os elementos que tem valores maiores que a raiz ficam na direita e os valores menores na esquerda(E essa regra vale para todos os nós da árvore).

Isso não vai fazer difereça na sua questão agora, porém, talvez vc tenha problemas na hora de encontrar elementos na árvore.

Seu código está incorreto

public int folhasqnt(){  
                    int d=0;  
                    int e=0;  
                    if([color=red][b]esq==null[/b] [/color])   o certo seria if([color=blue][b]esq!=null[/b] [/color])
                         e = esq.folhasqnt();  
                    else  
                         e=0;  
                    if([color=red][b]dir==null[/b] [/color])   o certo seria if([color=blue][b]dir!=null[/b] [/color])    
                         d = dir.folhasqnt();  
                    else  
                         d = 0;  
                           
                   return 1+e+d;     
                 }

Japaf 26 de nov. de 2010

Sim, eu fiz isso para encontrar o total de nós da árvore. Mas mudei para tentar encontrar a quantidade de nós folha, já que uma folha não tem nenhum filho…

Porém ainda estou com problemas na hora de encontrar a quantidade de nós folhas e somar os valores desses nós.

santanna106 26 de nov. de 2010

cara

do jeito que vc está fazendo a árvore não está sendo perrcorrida.

vc está chamando o método folhasqnt recurssivamente, mas, os nós não estão sendo visitados, pois em nenhum momento vc passa o próximo nó a ser perrcorrido pelo algoritmo.

veja se esse código funciona.

OBS: Eu não testei
[

public int folhasqnt( No raiz){  
          if(raiz!=null)  
                   folhasqnt(raiz.getEsquerda()) ;
                   folhasqnt(raiz.getDireita()) ;
                   if((raiz.getDireita() == null) && (raiz.getEsquerda() == null) ){
                      return 1;
}
                 return folhasqnt(raiz.getDireita() ) + folhasqnt( raiz.getEsquerda());
          }

santanna106 27 de nov. de 2010

O problema foi resolvido?

Criado 26 de novembro de 2010

Ultima resposta 27 de nov. de 2010

Respostas 6

Participantes 2

6 Respostas

Topicos relacionados