[JAVA] Alberi e Metodo Ricorsivo per contare le foglie

[luxorl]

Ciao,
ho come esercizio l'implementazione di un metodo ricorsivo con questa intestatura:

int calcola(AlberoBinario a)

che prende un albero binario e ritorna il numero di foglie che esso possiede.

Un albero binario è un insieme di nodi, che partono da un'unica radice e si raddoppiano ogni volta scendendo di livello... il nodo superiore è detto padre e i due nodi inferiori sono detti figli..

un nodo è detto foglia quando non possiede nessun figlio!!

Quindi il metodo deve ricorsivamente controllare tutti i nodi che non hanno nessun figlio e ritornarne l'esatto numero.

Questa è la soluzione a cui ho pensato.. sapreste dirmi se è giusta o se ho sbagliato qualcosa? Grazie

public int calcola(AlberoBinario a){
if(a==null) return 0;  //se l'albero è uguale a null vuol dire che è finito e io sono uscito fuori dall'ultima foglia
int f=0;
if(a.figlioSX==null&& a.figlioDX==null) f++; //supponendo che a.figlioSX e DX ritornino true se il nodo ha figlio e false altrimenti
f=calcola(a.figlioSX);
f=calcola(a.figlioDX);
return f+=f;
}

Spero di essere stato abbastanza chiaro! Grazie a chi vorrà darmi il suo parere

[luxorl]

up

[Galotar]

Originariamente inviato da luxorl

Ciao,
ho come esercizio l'implementazione di un metodo ricorsivo con questa intestatura:

int calcola(AlberoBinario a)

che prende un albero binario e ritorna il numero di foglie che esso possiede.

Un albero binario è un insieme di nodi, che partono da un'unica radice e si raddoppiano ogni volta scendendo di livello... il nodo superiore è detto padre e i due nodi inferiori sono detti figli..

un nodo è detto foglia quando non possiede nessun figlio!!

Quindi il metodo deve ricorsivamente controllare tutti i nodi che non hanno nessun figlio e ritornarne l'esatto numero.

Questa è la soluzione a cui ho pensato.. sapreste dirmi se è giusta o se ho sbagliato qualcosa? Grazie

public int calcola(AlberoBinario a){
if(a==null) return 0;  //se l'albero è uguale a null vuol dire che è finito e io sono uscito fuori dall'ultima foglia
int f=0;
if(a.figlioSX==null&& a.figlioDX==null) f++; //supponendo che a.figlioSX e DX ritornino true se il nodo ha figlio e false altrimenti
f=calcola(a.figlioSX);
f=calcola(a.figlioDX);
return f+=f;
}

Spero di essere stato abbastanza chiaro! Grazie a chi vorrà darmi il suo parere

Leggendo il codice tu assegni ad "f" prima il conteggio delle foglie dei figli sinistri e poi riassegni sempre ad "f" quelle del figlio destro : in ultima analisi ritorni f(foglie ramo destro) + se stesso.
Io farei cosi :

public int calcola(AlberoBinario a){
if(a==null) return 0;
if(a.figlioSX==null&& a.figlioDX==null) return 1;
int g=calcola(a.figlioSX);
int h=calcola(a.figlioDX);
return g+h;
}

Prova e fammi sapere.
Mii che pippe mentali

[71104]

Galotar, il tuo algoritmo ha un paio di problemi:
1) non devi ritornare g+h ma g+h+1
2) il secondo if è inutile

io lo farei così:

int calcola(AlberoBinario a) {
	if (null == a) {
		return 0;
	}
	return calcola(a.figlioSX) + calcola(a.figlioDX) + 1;
}

[Galotar]

Originariamente inviato da 71104

Galotar, il tuo algoritmo ha un paio di problemi:
1) non devi ritornare g+h ma g+h+1
2) il secondo if è inutile

io lo farei così:

int calcola(AlberoBinario a) {
	if (null == a) {
		return 0;
	}
	return calcola(a.figlioSX) + calcola(a.figlioDX) + 1;
}

1)Perchè devi aggiungiere 1?
2)Se Figlio è null non dovrebbe ritornare 0?

Fammi capire non ho capito perchè sono errori.

Edito : adesso ho capito credevo avessi levato l'if con il ritorno 0.
Cmq dovrebbe funzionare pure il mio di algoritmo,il tuo è più elegante ed efficiente sicuramente.

[Qu@ker]

Originariamente inviato da 71104

int calcola(AlberoBinario a) {
	if (null == a) {
		return 0;
	}
	return calcola(a.figlioSX) + calcola(a.figlioDX) + 1;
}

Questo pero' calcola il numero dei nodi, non delle foglie.

[71104]

Originariamente inviato da Galotar

1)Perchè devi aggiungiere 1?
2)Se Figlio è null non dovrebbe ritornare 0?

Fammi capire non ho capito perchè sono errori.

Edito : adesso ho capito credevo avessi levato l'if con il ritorno 0.
Cmq dovrebbe funzionare pure il mio di algoritmo,il tuo è più elegante ed efficiente sicuramente.

no, il mio non funziona perché ho letto solo adesso che l'algoritmo deve contare solo le foglie ^_^'
quello che ho scritto io conta tutti i nodi, invece per contare le foglie era corretto il tuo.

[71104]

Originariamente inviato da Qu@ker

Questo pero' calcola il numero dei nodi, non delle foglie.

appunto

[Galotar]

Originariamente inviato da 71104

no, il mio non funziona perché ho letto solo adesso che l'algoritmo deve contare solo le foglie ^_^'
quello che ho scritto io conta tutti i nodi, invece per contare le foglie era corretto il tuo.

Miii che caciara st'algoritmo