Pagina 1 di 2 1 2 ultimoultimo
Visualizzazione dei risultati da 1 a 10 su 20
  1. #1
    Utente di HTML.it
    Registrato dal
    Feb 2011
    Messaggi
    339

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

    Ciao a tutti.
    Dovrei realizzare un metodo ricorsivo in java che lavora su un albero binario.
    In particolare, deve verificare se gli elementi nelle foglie più profonde sono maggiori o uguali a zero.
    Non sono riuscito a capire come ricavare le foglie più profonde.
    Qualcuno mi può aiutare?
    Grazie anticipatamente.

  2. #2
    Utente di HTML.it L'avatar di andbin
    Registrato dal
    Jan 2006
    residenza
    Italy
    Messaggi
    18,254
    Quote Originariamente inviata da Markus85 Visualizza il messaggio
    Non sono riuscito a capire come ricavare le foglie più profonde.
    Beh, ovviamente serve andare "in profondità". Quindi per ciascun nodo ricorsivamente entri nel nodo "left" e poi in quello "right".
    Un nodo "foglia" è semplicemente quel nodo che ... non ha "figli" (quindi left e right sono null).
    Andrea, andbin.devSenior Java developerSCJP 5 (91%) • SCWCD 5 (94%)
    Java Versions Cheat Sheet

  3. #3
    Utente di HTML.it
    Registrato dal
    Feb 2011
    Messaggi
    339
    Quote Originariamente inviata da andbin Visualizza il messaggio
    Beh, ovviamente serve andare "in profondità". Quindi per ciascun nodo ricorsivamente entri nel nodo "left" e poi in quello "right".
    Un nodo "foglia" è semplicemente quel nodo che ... non ha "figli" (quindi left e right sono null).
    Potresti farmi un esempio di codice ?
    Io utilizzo questa interfaccia per lavorare sul'albero :
    codice:
    public interface AlberoBinario {
    int val(); //restituisce il valore memorizzato nella radice dell'albero
    public AlberoBinario destro(); //restituisce il sottoalbero destro dell'albero corrente
    public AlberoBinario sinistro(); // restituisce il sottoalbero sinistro dell'albero corrente
    }

  4. #4
    Utente di HTML.it L'avatar di andbin
    Registrato dal
    Jan 2006
    residenza
    Italy
    Messaggi
    18,254
    Quote Originariamente inviata da Markus85 Visualizza il messaggio
    Potresti farmi un esempio di codice ?
    Dovresti anche precisare cosa vuoi ottenere da un ipotetico metodo che definirai per questo compito. Hai detto infatti "verificare se gli elementi nelle foglie più profonde sono maggiori o uguali a zero". Vuoi verificare se quella condizione ce l'hanno tutte le foglie? O almeno una foglia? O vuoi il conteggio delle foglie che soddisfano quella condizione? O altro?
    Andrea, andbin.devSenior Java developerSCJP 5 (91%) • SCWCD 5 (94%)
    Java Versions Cheat Sheet

  5. #5
    Utente di HTML.it
    Registrato dal
    Feb 2011
    Messaggi
    339
    Quote Originariamente inviata da andbin Visualizza il messaggio
    Dovresti anche precisare cosa vuoi ottenere da un ipotetico metodo che definirai per questo compito. Hai detto infatti "verificare se gli elementi nelle foglie più profonde sono maggiori o uguali a zero". Vuoi verificare se quella condizione ce l'hanno tutte le foglie? O almeno una foglia? O vuoi il conteggio delle foglie che soddisfano quella condizione? O altro?
    Vorrei verificare se almeno una delle foglie più profonde contiene un valore maggiore o uguale a zero

  6. #6
    Utente di HTML.it
    Registrato dal
    Feb 2011
    Messaggi
    339
    Ho provato a buttar giù del codice... è giusto ?
    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());
    }
    }

  7. #7
    Utente di HTML.it L'avatar di andbin
    Registrato dal
    Jan 2006
    residenza
    Italy
    Messaggi
    18,254
    Quote Originariamente inviata da Markus85 Visualizza il messaggio
    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).
    Andrea, andbin.devSenior Java developerSCJP 5 (91%) • SCWCD 5 (94%)
    Java Versions Cheat Sheet

  8. #8
    Utente di HTML.it
    Registrato dal
    Feb 2011
    Messaggi
    339
    Mmmm....

    Provo a riscrivere il codice :

    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;
    }
    Ultima modifica di Markus85; 16-10-2018 a 17:45

  9. #9
    Utente di HTML.it L'avatar di andbin
    Registrato dal
    Jan 2006
    residenza
    Italy
    Messaggi
    18,254
    Quote Originariamente inviata da Markus85 Visualizza il messaggio
    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.
    Andrea, andbin.devSenior Java developerSCJP 5 (91%) • SCWCD 5 (94%)
    Java Versions Cheat Sheet

  10. #10
    Utente di HTML.it
    Registrato dal
    Feb 2011
    Messaggi
    339
    Vediamo...ci riprovo :
    codice:
    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;
    }

Permessi di invio

  • Non puoi inserire discussioni
  • Non puoi inserire repliche
  • Non puoi inserire allegati
  • Non puoi modificare i tuoi messaggi
  •  
Powered by vBulletin® Version 4.2.1
Copyright © 2024 vBulletin Solutions, Inc. All rights reserved.