[JAVA] Esercizio sugli alberi

[ziolu80]

Salve Ragazzi ho un problema informatico sugli alberi da risolvere
spero che qualcuno di voi possa aiutarmi.

Il problema è il seguente:
usando i metodi int val() =restituisce l'intero contenuto nella radice;
AlberoBinario des() restituisce il sottoalbero destro AlberoBinario sin() restituisce il sottoalbero sinistro, creare un metodo che ricevendo un albero binario restituisca true se tutte le foglie dell'albero contengono lo stesso valore della radice false altrimenti.

Ringrazio tutti per l'attenzione.

[Alex'87]

Stai cercando qualcuno che faccia l'esercizio al posto tuo? Hai sbagliato sezione, dovevi postare in Offro lavoro/collaborazione, più sotto.

[ziolu80]

Originariamente inviato da Alex'87
Stai cercando qualcuno che faccia l'esercizio al posto tuo? Hai sbagliato sezione, dovevi postare in Offro lavoro/collaborazione, più sotto.

No un suggerimeto un idea perchè non so proprio come fare tutto qui. P.s Complimenti per la simpatia!

[satifal]

Basta utilizzare un metodo ricorsivo per navigare l'albero.

[alka]

Originariamente inviato da ziolu80
No un suggerimeto un idea perchè non so proprio come fare tutto qui.

Abbozza una soluzione o un ragionamento, e vedremo di aiutarti.

Se non sai proprio dove partire, allora significa che probabilmente non ti sei documentato abbastanza, quindi l'unico aiuto che ti si può dare è svolgere l'esercizio.

Originariamente inviato da ziolu80
P.s Complimenti per la simpatia!

Si tratta di ovvietà: dare una mano è una questione, fare i compiti a casa degli altri è un'altra.

Posta il codice della soluzione che pensi di adottare, e vedremo di correggerla, oppure spiega nel dettaglio cosa non riesci a fare.

[ziolu80]

Originariamente inviato da alka
Abbozza una soluzione o un ragionamento, e vedremo di aiutarti.

Se non sai proprio dove partire, allora significa che probabilmente non ti sei documentato abbastanza, quindi l'unico aiuto che ti si può dare è svolgere l'esercizio.




Si tratta di ovvietà: dare una mano è una questione, fare i compiti a casa degli altri è un'altra.

Posta il codice della soluzione che pensi di adottare, e vedremo di correggerla, oppure spiega nel dettaglio cosa non riesci a fare.

questa è la mia soluzione :

private static boolean noFigli(AlberoB a){
if(a==null)return false;
return a.getDes()==null && a.getSin()==null;
}



private static boolean nodiUguali(AlberoB a,int radice){


if(a!=null || !noFigli(a)){

if(noFigli(a.getDes())&& noFigli(a.getSin())){
return(Integer)a.getDes().getVal()==radice && (Integer)a.getSin().getVal()==radice;
}
else if(noFigli(a.getSin()) && (!noFigli(a.getDes()))||a.getDes()==null){
return(Integer)a.getSin().getVal()==radice;
}else if(noFigli(a.getDes())&& (!noFigli(a.getSin()))|| a.getSin()==null)
return(Integer)a.getDes().getVal()==radice;



}
return nodiUguali(a.getDes(),radice) && nodiUguali(a.getSin(),radice) ;


}



private static boolean analizzaNodiFoglia(AlberoB a){

int radice=(Integer)a.getVal();
return nodiUguali(a,radice);

}





public static void main(String[] args) {
AlberoBImpl a= new AlberoBImpl(0);
AlberoBImpl des=new AlberoBImpl(3);
AlberoBImpl desd=new AlberoBImpl(0);
AlberoBImpl dess=new AlberoBImpl(0);
AlberoBImpl sin=new AlberoBImpl(6);
AlberoBImpl sind=new AlberoBImpl(0);
des.setDes(desd);
des.setSin(dess);
sin.setDes(sind);
a.setDes(des);
a.setSin(sin);








System.out.println(analizzaNodiFoglia(a));



}



}

se l'albero ha dei figli il programma funziona me si passo un null oppure un albero senza figli cioè solo la radice mi restituisce un null point exception alla linea di codice return nodiUguali(a.getDes(),radice) && nodiUguali(a.getSin(),radice). Come posso risolvere ?

Ps AlberoBImpl è implementazione dell'interfaccia AlberoB, getDes() restituisce il sotto albero destro getSin() restituisce il sotto albero sinistro getVal() restituisce il contenuto della radice e setDes e setSin permettono di settare , rispettivamente con un albero il sotto albero destro e sinistro. Questa classe si basa su un albero binario.
Grazie a tutti per l'attenzione e la cortesia.

[ziolu80]

Originariamente inviato da ziolu80
questa è la mia soluzione :

private static boolean noFigli(AlberoB a){
if(a==null)return false;
return a.getDes()==null && a.getSin()==null;
}



private static boolean nodiUguali(AlberoB a,int radice){


if(a!=null || !noFigli(a)){

if(noFigli(a.getDes())&& noFigli(a.getSin())){
return(Integer)a.getDes().getVal()==radice && (Integer)a.getSin().getVal()==radice;
}
else if(noFigli(a.getSin()) && (!noFigli(a.getDes()))||a.getDes()==null){
return(Integer)a.getSin().getVal()==radice;
}else if(noFigli(a.getDes())&& (!noFigli(a.getSin()))|| a.getSin()==null)
return(Integer)a.getDes().getVal()==radice;



}
return nodiUguali(a.getDes(),radice) && nodiUguali(a.getSin(),radice) ;


}



private static boolean analizzaNodiFoglia(AlberoB a){

int radice=(Integer)a.getVal();
return nodiUguali(a,radice);

}





public static void main(String[] args) {
AlberoBImpl a= new AlberoBImpl(0);
AlberoBImpl des=new AlberoBImpl(3);
AlberoBImpl desd=new AlberoBImpl(0);
AlberoBImpl dess=new AlberoBImpl(0);
AlberoBImpl sin=new AlberoBImpl(6);
AlberoBImpl sind=new AlberoBImpl(0);
des.setDes(desd);
des.setSin(dess);
sin.setDes(sind);
a.setDes(des);
a.setSin(sin);








System.out.println(analizzaNodiFoglia(a));



}



}

se l'albero ha dei figli il programma funziona me si passo un null oppure un albero senza figli cioè solo la radice mi restituisce un null point exception alla linea di codice return nodiUguali(a.getDes(),radice) && nodiUguali(a.getSin(),radice). Come posso risolvere ?

Ps AlberoBImpl è implementazione dell'interfaccia AlberoB, getDes() restituisce il sotto albero destro getSin() restituisce il sotto albero sinistro getVal() restituisce il contenuto della radice e setDes e setSin permettono di settare , rispettivamente con un albero il sotto albero destro e sinistro. Questa classe si basa su un albero binario.
Grazie a tutti per l'attenzione e la cortesia.

Ragazzi ho risolto era molto semplice basta cambiare il metodo analizzaNodiFoglia così:




private static boolean analizzaNodiFoglia(AlberoB a){
if(a==null||noFigli(a))retrun false;
int radice=(Integer)a.getVal();
return nodiUguali(a,radice);

}


grazie a tutti per le risposte.
Vorrei chiedere se fosse possibile sapere la complessità temporale e spaziale del metodo analizzaNodiFoglia nel caso peggiore e migliore.



Lascio il codice potrebbe servire a qualcun'altro.