spiegazione del programma che implementa gli alberi in java

Discussione in 'Java' iniziata da aneres, 23 Maggio 2012.

  1. aneres

    aneres Nuovo Utente

    Registrato:
    27 Febbraio 2012
    Messaggi:
    21
    Mi Piace Ricevuti:
    0
    Punteggio:
    0
    ciao
    ho il seguente programma , il quale riporta i metodi di inserimento cancellazione e ricerca di un nodo ....
    me lo potete spiegare mettendo magari dei commenti ai vari metodi , spiegandomi per bene come agiscono?
    grazie
    Codice:
    import java.io.*;
    import java.util.Scanner;
    
    
    class Nodo
    {
         int value;
         Nodo left;
         Nodo right;
         boolean eliminato;
    
    
       public Nodo(int value)
       {
           this.value=value;
           left=null;
           right=null;
           eliminato=false;
    
       }
       
    }
    
    
      class AlberoBinario{
       Nodo root;
    public AlberoBinario()
    {
    root= null;
    }
       public void inserisciValore(Nodo nuovo)
        {
          
          if(root== null)
          {
              root=nuovo;
          }else
              inserisciValore(nuovo,root);
       }
             void inserisciValore(Nodo nuovo,Nodo n)
            {
                if(nuovo.value==n.value)
                {
                    n.eliminato=false;
                }else if(nuovo.value<n.value)
                {
                    if(n.left==null)
                    {
                        n.left=nuovo;
                    }else
                    {
                        inserisciValore(nuovo,n.left);
                   }
                }
               else{
                    if(n.right==null)
                    {
                        n.right=nuovo;
                    }else
                    {
                        inserisciValore(nuovo,n.right);
                    }
                 }
            }
      
    
    
    
    public void elimina(int el)
    {
        elimina(el,root);
    }
    
     void elimina(int el,Nodo n)
      {
          if(n !=null)
          {
              if(el==n.value)
              {
                  n.eliminato=true;
                  System.out.println("valore eliminato");
              }else
                  if(el<n.value)
                      elimina(el,n.left);
          else
              elimina(el,n.right);
          }
       else
           System.out.println ("valore non  trovato");
      }
    
        Nodo ricerca(int cerca){
            return ricerca(cerca, root);
        }
        Nodo ricerca(int cerca, Nodo n){
            if(n!=null)
                if(cerca==n.value)
                    if(n.eliminato)
                        return null;
                    else
                        return n;
                else if(cerca<n.value)
                    return ricerca(cerca, n.left);
                else
                    return ricerca(cerca, n.right);
            else
                return null;
        }
      }
    class Main
    {
        public static void main(String[]args)
        {
             Alberoiterativo ai= new Alberoiterativo();
             ai.Alberoiterativo();
        }
    }
    
    public class Alberoiterativo {
      AlberoBinario a;
        Scanner t = new Scanner(System.in);
          void Alberoiterativo()
        {
            
             a=new AlberoBinario();
            int scelta;
           while (true) {
          
          System.out.println("1. Inserisci elemento");
          System.out.println("2. Ricerca elemento");
          System.out.println("3. Elimina elemento.");
          System.out.println("4. Esci");
          System.out.println();
          System.out.print("Selezionare un'operazione da eseguire: ");
          scelta = t.nextInt();
          System.out.println();
          switch (scelta) {
            case 1:  
              aggiunta(); 
              break;
            case 2: 
              contiene();
              break;
            case 3:
                eliminazione(); 
                break;
            case 4:
              System.exit(1);
              break;
        }
           }
    
          }
            public void aggiunta()
            {
                Nodo n;
                int id;
                System.out.print("inserisci valore: ");
                id=t.nextInt();
                n=new Nodo(id);
                a.inserisciValore(n);
            }
    
            public void eliminazione()
            {
                int id;
                System.out.print("inserisci il valore da eliminare: ");
                id=t.nextInt();
                a.elimina(id);
            }
             public void contiene()
            {
    
                int id;
                System.out.print("inserisci il valore da ricercare: ");
                id=t.nextInt();
                if(a.ricerca(id)==null)
                    System.out.println("valore non trovato");
                else
                    System.out.println("valore trovato");
            }
        }
     
  2. andre9004

    andre9004 Utente Attivo

    Registrato:
    15 Marzo 2012
    Messaggi:
    104
    Mi Piace Ricevuti:
    1
    Punteggio:
    0
    Occupazione:
    Studente
    Località:
    Lombardia
    Codice:
    import java.io.*;
    import java.util.Scanner;
    
    
    class Nodo
    {
         int value;
         Nodo left;
         Nodo right;
         boolean eliminato;
    
    
       public Nodo(int value)
       {
           this.value=value;
           left=null;
           right=null;
           eliminato=false;
    
       }
       
    }
    
    
      class AlberoBinario{
       Nodo root;
    public AlberoBinario()
    {
    root= null;
    }
       public void inserisciValore(Nodo nuovo)
        {
          
          if(root== null)
          {
              root=nuovo;
          }else
              inserisciValore(nuovo,root);
       }
             void inserisciValore(Nodo nuovo,Nodo n)
            {
                if(nuovo.value==n.value)
                {
                    n.eliminato=false;
                }else if(nuovo.value<n.value)
                {
                    if(n.left==null)
                    {
                        n.left=nuovo;
                    }else
                    {
                        inserisciValore(nuovo,n.left);
                   }
                }
               else{
                    if(n.right==null)
                    {
                        n.right=nuovo;
                    }else
                    {
                        inserisciValore(nuovo,n.right);
                    }
                 }
            }
      
    
    
    
    public void elimina(int el)
    {
        elimina(el,root);
    }
    
     void elimina(int el,Nodo n)
      {
          if(n !=null)
          {
              if(el==n.value)
              {
                  n.eliminato=true;
                  System.out.println("valore eliminato");
              }else
                  if(el<n.value)
                      elimina(el,n.left);
          else
              elimina(el,n.right);
          }
       else
           System.out.println ("valore non  trovato");
      }
    
        Nodo ricerca(int cerca){
            return ricerca(cerca, root);
        }
        Nodo ricerca(int cerca, Nodo n){
            if(n!=null)
                if(cerca==n.value)
                    if(n.eliminato)
                        return null;
                    else
                        return n;
                else if(cerca<n.value)
                    return ricerca(cerca, n.left);
                else
                    return ricerca(cerca, n.right);
            else
                return null;
        }
      }
    class Main
    {
        public static void main(String[]args)
        {
             Alberoiterativo ai= new Alberoiterativo();
             ai.Alberoiterativo();
        }
    }
    
    public class Alberoiterativo {
      AlberoBinario a;
        Scanner t = new Scanner(System.in);
          void Alberoiterativo()
        {
            
             a=new AlberoBinario();
            int scelta;
           while (true) {
          
          System.out.println("1. Inserisci elemento");
          System.out.println("2. Ricerca elemento");
          System.out.println("3. Elimina elemento.");
          System.out.println("4. Esci");
          System.out.println();
          System.out.print("Selezionare un'operazione da eseguire: ");
          scelta = t.nextInt();
          System.out.println();
          switch (scelta) {
            case 1:  
              aggiunta(); 
              break;
            case 2: 
              contiene();
              break;
            case 3:
                eliminazione(); 
                break;
            case 4:
              System.exit(1);
              break;
        }
           }
    
          }
            public void aggiunta()
            {
                Nodo n;
                int id;
                System.out.print("inserisci valore: ");
                id=t.nextInt();
                n=new Nodo(id);
                a.inserisciValore(n);
            }
    
            public void eliminazione()
            {
                int id;
                System.out.print("inserisci il valore da eliminare: ");
                id=t.nextInt();
                a.elimina(id);
            }
             public void contiene()
            {
    
                int id;
                System.out.print("inserisci il valore da ricercare: ");
                id=t.nextInt();
                if(a.ricerca(id)==null)
                    System.out.println("valore non trovato");
                else
                    System.out.println("valore trovato");
            }
        }
    chi l'ha fatto il codice? ci sarebbero un po di errori da correggere... come l'accesso ai campi della classe nodo dalla classe albero binario con il . cosa sbagliattissima da fare e poi alcuni errori strutturali... come il nodo left e right della classe nodo... se vuoi ti aiuto a riscriverla meglio e intanto te la spiego... dimmi te
     
  3. aneres

    aneres Nuovo Utente

    Registrato:
    27 Febbraio 2012
    Messaggi:
    21
    Mi Piace Ricevuti:
    0
    Punteggio:
    0
    l'ho copiato da delle fotocopio date dalla prof..certo se ti va di aiutarmi a scriverlo meglio volentieri non mi dispiace..e sì se me lo spieghi non sarebbe male..mi servirebbe per domani mattina... vedi tu se riesci..grazie :)
     
  4. andre9004

    andre9004 Utente Attivo

    Registrato:
    15 Marzo 2012
    Messaggi:
    104
    Mi Piace Ricevuti:
    1
    Punteggio:
    0
    Occupazione:
    Studente
    Località:
    Lombardia
    o c** l'ho letto ora :skull: serve ancora?
     
  5. aneres

    aneres Nuovo Utente

    Registrato:
    27 Febbraio 2012
    Messaggi:
    21
    Mi Piace Ricevuti:
    0
    Punteggio:
    0
    sì sì almeno lo leggo e lo studio e cerco di capire:)
     
  6. andre9004

    andre9004 Utente Attivo

    Registrato:
    15 Marzo 2012
    Messaggi:
    104
    Mi Piace Ricevuti:
    1
    Punteggio:
    0
    Occupazione:
    Studente
    Località:
    Lombardia
    ok ora mi metto su e lo faccio :byebye:
     
  7. andre9004

    andre9004 Utente Attivo

    Registrato:
    15 Marzo 2012
    Messaggi:
    104
    Mi Piace Ricevuti:
    1
    Punteggio:
    0
    Occupazione:
    Studente
    Località:
    Lombardia
    Codice:
    import java.io.*;
    import java.util.Scanner;
    
    //Ho rimosso la classe nodo poichè secondo me non serve... 
    
      //classe albero binario 
      class AlberoBinario{
       //radice o informazione dell'albero
       int value;
       
       //nodo sinistro e destro
       AlberoBinario sx,dx;
       
       //primo costruttore che serve a creare un "nodo" con solo l'informazione o la radice
       AlberoBinario(){
    		sx=null;
    		dx=null;
      }
      
      //secondo costruttore che invece mi crea un albero con nodo destro sinistro e informazione o radice
      AlberoBinario(int value, AlberoBinario sx, AlberoBinario dx){
    		this.value=value;
    		this.sx=sx;
    		this.dx=dx;
      }
      
      //terzo costruttore che ha solo il nodo destro e sinistro poichè magari fa parte di un altro nodo.
      AlberoBinario(AlberoBinario sx,AlberoBinario dx){
    		this.sx=sx;
    		this.dx=dx;
      }
      
    		//metodo che se non ho capito male in base all'informazione capisci o no se il nodo deve essere destro o
    		//sinistro e quindi lo crei/riinizializzi .. è meglio se usi un metodo getValue() che ti restituisce l'informazione e un setNodo() che
    		//ti setta il nodo della classe AlberoBinario in modo da non usare il .
             void inserisciValore(AlberoBinario nuovo, AlberoBinario n)
            {
                if(nuovo.value==n.value)
                {
                    n.eliminato=false;
                }else if(nuovo.value<n.value)
                {
                    if(n.sx==null)
                    {
                        n.sx=nuovo;
                    }else
                    {
                        inserisciValore(nuovo,n.sx);
                   }
                }
               else{
                    if(n.dx==null)
                    {
                        n.dx=nuovo;
                    }else
                    {
                        inserisciValore(nuovo,n.dx);
                    }
                 }
            }
      
    
    
    // io farei un metodo elimina e non due (non hanno senso perchè il vecchio nodo root che ho tolto era un campo e quindi richiamabile benissimo
    //senza parametro
    
     void elimina(int el, AlberoBinario alberoBinario)
      {
          if(alberoBinario.getSx() !=null)
          {
              if(el==alberoBinario.getSx().getValue())
              {
                  alberoBinario.setSx()=null;
                  System.out.println("valore eliminato");
              }else
                  if(el<alberoBinario.getSx().getValue())
                      elimina(el,alberoBinario.getSx());
          else
              elimina(el,alberoBinario.getDx());
          }
       else
           System.out.println ("valore non  trovato");
      }
    	
    	//ricerca del nodo sia sx che dx
        Nodo ricerca(int cerca, AlberoBinario alberoBinario){
    	
    	//VA Aggiustato come ho fatto con il metodo elimina... e bisogna aggiungere la ricerca del nodo anche in quello destro
            if(n!=null)
                if(cerca==n.value)
                    if(n.eliminato)
                        return null;
                    else
                        return n;
                else if(cerca<n.value)
                    return ricerca(cerca, n.left);
                else
                    return ricerca(cerca, n.right);
            else
                return null;
        }
      }
      
     // classe main
    public class Main
    {
        public static void main(String[]args)
        {
             AlberoBinario ai= new Alberoiterativo();
             ai.Alberoiterativo();
        }
    }
    
    //perchè creare un'altra classe quando queste operazioni le puoi mettere nel main??
    public class Alberoiterativo {
    
    //oggetto albero binario
      AlberoBinario a;
        Scanner t = new Scanner(System.in);
          void Alberoiterativo()
        {
    		//va costruito in base a come lo vuoi... quindi con l'uso di uno dei tre costruttori
             a=new AlberoBinario();
    		 
    		 //variabile x acquisizione da tastiera
            int scelta;
    		
    		//inizio operazioni
           while (true) {
          
    	  //menu e operazioni
          System.out.println("1. Inserisci elemento");
          System.out.println("2. Ricerca elemento");
          System.out.println("3. Elimina elemento.");
          System.out.println("4. Esci");
          System.out.println();
          System.out.print("Selezionare un'operazione da eseguire: ");
          scelta = t.nextInt();
          System.out.println();
          switch (scelta) {
            case 1:  
              aggiunta(); 
              break;
            case 2: 
              contiene();
              break;
            case 3:
                eliminazione(); 
                break;
            case 4:
    		//io avrei usato una variabile booleana inizializzata a true nel while e l'avrei impostata a false qui
              System.exit(1);
              break;
        }
           }
    
          }
            public void aggiunta()
            {
                Nodo n;
                int id;
                System.out.print("inserisci valore: ");
                id=t.nextInt();
                n=new Nodo(id);
                a.inserisciValore(n);
            }
    
            public void eliminazione()
            {
                int id;
                System.out.print("inserisci il valore da eliminare: ");
                id=t.nextInt();
                a.elimina(id);
            }
             public void contiene()
            {
    
                int id;
                System.out.print("inserisci il valore da ricercare: ");
                id=t.nextInt();
                if(a.ricerca(id)==null)
                    System.out.println("valore non trovato");
                else
                    System.out.println("valore trovato");
            }
        }
    Noi l'abbiamo fatto cosi' a scuola a parte alcuni metodi di eliminazione e ricerca... comunque non capisco perchè usare un metodo che richiama un altro metodo... cioè richiama subito un metodo senza farne due!! e cosi con la classe albero iterativo... bo...

    Magari c'ho piazzato qualche errore anchio eheheh ma il nostro prof è fissato con java percui ci ha messo in testa cose, in teoria, corrette :p
     
  8. aneres

    aneres Nuovo Utente

    Registrato:
    27 Febbraio 2012
    Messaggi:
    21
    Mi Piace Ricevuti:
    0
    Punteggio:
    0
    ti ringrazio moltissimo :)))
     
Sto caricando...

Condividi questa Pagina