spiegazione del programma che implementa gli alberi in java

aneres

Nuovo Utente
27 Feb 2012
21
0
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");
        }
    }
 

andre9004

Utente Attivo
15 Mar 2012
104
1
0
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
 

aneres

Nuovo Utente
27 Feb 2012
21
0
0
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
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 :)
 

andre9004

Utente Attivo
15 Mar 2012
104
1
0
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
 

aneres

Nuovo Utente
27 Feb 2012
21
0
0
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
ti ringrazio moltissimo :)))