Visualizzazione dei risultati da 1 a 5 su 5
  1. #1
    Utente di HTML.it
    Registrato dal
    Feb 2011
    Messaggi
    339

    Alberi Binari , metodo ricorsivo per verificare se tutti gli elementi di un albero a, sono presenti anche in un albero b

    Ciao.
    Di seguito posto il codice che ho scritto per verificare in maniera ricorsiva se e solo se , tutti gli elementi presenti in un albero binario a , sono presenti anche in un albero binario b.
    Correggetemi se sbaglio.

    Interfaccia:

    codice:
    public interface AlberoBinario{
    
       public AlberoBinario destro(); //restituisce il sottoalbero destro dell'albero corrente
       public AlberoBinario snistro(); //restituisce il sottoalbero sinistro dell'albero corrente
       public in val(); //restituisce il valore memorizzato nella radice dell'albero
    Metodo per la verifica:

    codice:
    public static boolean verifica(AlberoBinario a, AlberoBinario b){
    
       if(a==null) return true;
        if(presente(b,a.val()){
         boolean b = verifica(a.destro());
          if(b) return verifica(a.sinistro());
        }
        return false;
    }
    
    boolean presente(AlberoBinario a , int v){
      if(a==null) return false;
      if(a.val() != v){
        boolean b = presente(a.destro(), v);
         if(b) return presente(a.sinistro(),v);
      }
      return false;
    }

  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
    Correggetemi se sbaglio.
    E' sbagliato. Innanzitutto in verifica fai la ricorsione passando 1 solo argomento. Poi in presente se a.val() È uguale a v, tu restituisci false. Che non è giusto. Stesso discorso poi già fatto del OR "logico" che si può usare.

    Non ho analizzato in dettaglio, comunque.
    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
    E' sbagliato. Innanzitutto in verifica fai la ricorsione passando 1 solo argomento. Poi in presente se a.val() È uguale a v, tu restituisci false. Che non è giusto. Stesso discorso poi già fatto del OR "logico" che si può usare.

    Non ho analizzato in dettaglio, comunque.
    Ah scusa...mi è sfuggito un parametro...
    Riscrivo :

    codice:
    public static boolean verifica(AlberoBinario a, AlberoBinario b){
     if(a==null) return true;
      if(presente(b, a.val()){
        verifica(a.destro(), b) || verifica(a.sinistro(), b) ;
      }
     return false;
    }
    
    boolean presente(AlberoBinario a, int v){
     if(a==null) return false;
      if(a.val() != v){
        presente(a.destro(),v) || presente(a.sinistro(), v);
      }
      return true;
    }

  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
    Ah scusa...mi è sfuggito un parametro...
    Riscrivo :
    Dovrei verificarlo meglio. Ma ... stesso problema dell'altra discussione. I return !!

    verifica(a.destro(), b) || verifica(a.sinistro(), b)

    è una espressione che messa da sola lì serve a poco. Sono due boolean messi in OR "logico". Il risultato è un boolean. Questo boolean lo DEVI usare (nei tuoi metodi sopra, cioè da restituire)
    Andrea, andbin.devSenior Java developerSCJP 5 (91%) • SCWCD 5 (94%)
    Java Versions Cheat Sheet

  5. #5
    Utente di HTML.it L'avatar di andbin
    Registrato dal
    Jan 2006
    residenza
    Italy
    Messaggi
    18,254
    Osserva il metodo 'presente', a parte il primo test di a==null con return false (che è giusto), deve restituire true quando: il valore lo trovi in quel nodo oppure lo trovi sotto il nodo a destra oppure lo trovi sotto il nodo a sinistra.
    Nota gli "oppure" che ho scritto. Traducili in codice.
    Andrea, andbin.devSenior Java developerSCJP 5 (91%) • SCWCD 5 (94%)
    Java Versions Cheat Sheet

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.