Gin&&Tonic
06-08-2010, 10:30
Ho svolto questo esercizio, ma non sono sicuro che funzioni(posto traccia e soluzione sperando in qualche correzione):
Si consideri la seguente interfaccia che descrive alberi binari in cui la parte
informativa di ogni nodo sia un intero.
public interface AlberoBinario{
int val();
AlberoBinario sin();
AlberoBinario des();
}
Implementare il metodo
boolean Controllo(AlberoBinario a, AlberoBinario b);
che restituisce vero se e solo se tutti i valori contenuti nell’albero a sono contenuti
anche nell’albero b
.
(si ricorda che si possono implementare tutti i metodi di appoggio che si ritiene utili per l’implementazione del metodo Controllo).
Soluzione:
//creo un metodo esiste
public static boolean esiste(int n,AlberoBinario B){
if(B==null) return false;
//se non esiste il sotto albero ritorno false
else if(B.val()==n) return true;
else return esiste(n,B.destro()) || esiste(n,B.sinistro());
}
soluzione controllo:
public static boolean controllo(Albero a,Albero b){
//caso in cui i "sotto alberi non esistono", devo tornare per forza true perchè il risultato finale di controlo sara dato da un "and"
if(a==null)return true;
return esiste(a.val(),b) && controllo(a.destro(),b) && controllo(a.sinistro(),b);
}
Si consideri la seguente interfaccia che descrive alberi binari in cui la parte
informativa di ogni nodo sia un intero.
public interface AlberoBinario{
int val();
AlberoBinario sin();
AlberoBinario des();
}
Implementare il metodo
boolean Controllo(AlberoBinario a, AlberoBinario b);
che restituisce vero se e solo se tutti i valori contenuti nell’albero a sono contenuti
anche nell’albero b
.
(si ricorda che si possono implementare tutti i metodi di appoggio che si ritiene utili per l’implementazione del metodo Controllo).
Soluzione:
//creo un metodo esiste
public static boolean esiste(int n,AlberoBinario B){
if(B==null) return false;
//se non esiste il sotto albero ritorno false
else if(B.val()==n) return true;
else return esiste(n,B.destro()) || esiste(n,B.sinistro());
}
soluzione controllo:
public static boolean controllo(Albero a,Albero b){
//caso in cui i "sotto alberi non esistono", devo tornare per forza true perchè il risultato finale di controlo sara dato da un "and"
if(a==null)return true;
return esiste(a.val(),b) && controllo(a.destro(),b) && controllo(a.sinistro(),b);
}