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.
[code] 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;
} [/code]
Executando esse código retorna apenas 1.
Quando fiz para retornar a quantidade geral de nós só mudava o if para
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;
}
}
[/code]
Classe Bnode:
[code]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;
}
}[/code]
Segue todo o código.
Obrigado pelo interesse em ajudar.
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;
}
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.
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());
}