Albero Binario , metodo ricorsivo per verificare i valori delle foglie più profonde

[Markus85]

Ho provato a buttar giù del codice... è giusto ?

public static boolean verifica(AlberoBinario a){
if(a==null) return false;
if(a.sinistro() == null && a.destro() == null){
if(a.val() >=0) return true;
else{
boolean b = verifica(a.destro());
if (!b) return verifica(a.sinistro());
}
}

[andbin]

Ho provato a buttar giù del codice... è giusto ?

No, non è giusto. Testi if(a.sinistro() == null && a.destro() == null) (che testa se a è "foglia") e poi dentro il corpo del if vai in ricorsione (che non ha senso perché per la condizione del if sarebbe una foglia).

[Markus85]

Mmmm....

Provo a riscrivere il codice :

public static boolean verifica(AlberoBinario a){
 if(a==null) return false;
  if(a.sinistro()==null && a.destro()==null){
    if(a.val()>=0) return true;
  }
  else{
     boolean b = verifica(a.destro());
      if(!b) return verifica(a.sinistro());
  }
 return false;
}

[andbin]

Mi puoi correggere il codice?

Dove devo fare la ricorsione?

Il primo test del a==null è assolutamente giusto/sensato.

Poi dovrai testare se è una foglia (entrambi sinistro/destro a null). Se è una foglia, testi la condizione specifica sul valore. In base alla condizione, restituisci SUBITO true o false (non serve un if ... basta l'espressione della condizione). Questo perché è una foglia ... non hai nulla sotto.

Se non sei entrato nel if della foglia .... allora NON è una foglia. Quindi:
- se c'è il sinistro, entri ricorsivamente nel sinistro
- se c'è il destro, entri ricorsivamente nel destro

C'è una considerazione da fare: entrambe le chiamate ricorsive restituiscono un boolean. Cosa restituisci al "di sopra"? Semplice: tu hai detto "almeno una delle foglie". Quindi se dal sinistro ottieni già true, non hai più da entrare nel destro!

Se né dal sinistro, né dal destro ottieni un true .... ovviamente restituisci false.

[Markus85]

Vediamo...ci riprovo :

public static boolean verifica(AlberoBinario a){
 if(a==null) return false;
  if(a.destro()==null && a.sinistro()==null){
    if(a.val()>=0) return true;
     else return false;
  }
  else{
    boolean b = verifica(a.destro());
     if(!b) return verifica(a.sinistro());
  }
 return false;
}

[andbin]

Vediamo...ci riprovo

No, non ancora. Innanzitutto nel caso di foglia puoi semplificare il return. Dicevo prima: non serve per forza un if .... hai l'espressione della condizione che è .... un boolean!

Nella parte finale, neanche. Va bene sfruttare quel a==null iniziale per poter invocare comunque verifica ricorsivamente. Ma se b è true, non restituisci al chiamante true!

E nella parte finale puoi comunque semplificare molto: quale è quell'operatore che verifica se almeno uno dei due operandi è true e se il primo è true NON valuta il secondo operando?

[Markus85]

Beh...Mi butteresti quattro righe di codice?
Giusto per avere maggior chiarezza della soluzione.

Intanto ci riprovo nuovamente :-)

public static boolean verifica(AlberoBinario a){
  if(a==null) return false;
   if(a.sinistro()==null && a.destro()==null) return a.val()>=0;
    else{
      boolean b = verifica(a.destro());
       if(!b) return verifica(a.sinistro());
    }
   return true;
}