//******************************************************
//   Classe Albero.java
//   Rappresenta una struttura ad albero binario
//******************************************************

public class Albero {
   
   private NodoAlbero a;
      
   public Albero() {
      a = null;
   }
   
   private static class NodoAlbero {
      private Comparable dato;
      private Albero sx, dx;
   }
   
   public String toString(String separatore) {
      if (a != null) {
         String sinistra = a.sx.toString(separatore);
         String centro = a.dato.toString() + separatore;
         String destra = a.dx.toString(separatore);
         return sinistra + centro + destra;
      } else
          return "";
   }

//  public String toString() {
//       return this.toString("\t");
//   }

   public void attraversa_SRD() {
      if (a != null) {
         a.sx.attraversa_SRD();
         System.out.println(a.dato);
         a.dx.attraversa_SRD();
      }
   }
   
 	public void attraversa_RSD() 
	{
      if (a != null) {
         System.out.println(a.dato);
		 a.sx.attraversa_RSD();
         a.dx.attraversa_RSD();
      }
   }
   
 	public void attraversa_SDR() 
	{
      if (a != null) {
         a.sx.attraversa_SDR();
         a.dx.attraversa_SDR();
         System.out.println(a.dato);
      }
   }
   
   public NodoAlbero init (Comparable x)
   {
   		NodoAlbero tmp = new NodoAlbero();
        tmp.dato = x;
        tmp.sx = new Albero();
        tmp.dx = new Albero();
		return tmp;
   }
   
   public void inserisci(Comparable x) 
   {
  		if (a == null) {
        	a = init (x);
      	} else if (x.compareTo(a.dato) < 0)
         	a.sx.inserisci(x);
      	else
         	a.dx.inserisci(x);
   }

   public Comparable trova(Comparable x) {
      if (a == null)
         return null;
      else if (x.compareTo(a.dato) < 0)
         return a.sx.trova(x);
      else if (x.compareTo(a.dato) > 0)
         return a.dx.trova(x);
      else
         return a.dato;
   }

   public Comparable trovaEInserisci(Comparable x) {
      if (a == null) {
         a = new NodoAlbero();
         a.dato = x;
         a.sx = new Albero();
         a.dx = new Albero();
		 return null;
      } else if (x.compareTo(a.dato) < 0)
         return a.sx.trovaEInserisci(x);
      else if (x.compareTo(a.dato) > 0)
         return a.dx.trovaEInserisci(x);
      else
         return a.dato;
   }
   
   public boolean vuoto() {
      return a == null;
   }
   
}