import java.awt.*;
import java.applet.*;
 
class Arbore                                     // Implementarea unui Arbore
{
   
   // ---- Membrii ---- //
   
   private Nod radacina;                         // Radacina Arborelui   
   
   private int dimArbore;                        // dimensiunea arborelui (numarul de noduri) 
   
   private Arbore parinte;                       // parintele nodului curent
   
   private Arbore left;                          // referinta catre nodul din stanga
   
   private Arbore right;                         // referinta catre nodul din dreapta

   private DesenNod nod;                         // corespondentul grafic al nodului din Arbore
   
   private int centru;                           // pozitia in care se deseneaza nodul (centrul acestuia)
   
   private int leftCentru;                       // centrul in care se deseneaza fiul nodului curent din stanga
   
   private int rightCentru;                      // centrul in care se deseneaza fiul nodului curent din dreapta
   
   private ExprLogic e;                          // expresia formulei 

   // ---- Metode ---- //


   Arbore(Nod r)                                 // Constructorul 1
   {
      radacina = new Nod(r);                     // constructorul nodului 
      dimArbore = 1;                             // dimensiunea 1 (un nod)
      nod = new DesenNod();
      centru= 0;      
      leftCentru= 0;
      rightCentru= 0;
   }
   
   Arbore ()
   { //radacina = null;
    // dimArbore = 0;
   } 

   Arbore nouLeft(Nod elem)                      // Constructorul 2 
   {
      left = new Arbore(elem);                   // creeaza nodul stang
      //left.parinte = this;
      left.nod = new DesenNod();      
      return left;
   }

   Arbore nouRight(Nod elem)                     // Constructorul 3
   {
      right= new Arbore(elem);                   // creeaza nodul drept
     // right.parinte = this;
      right.nod = new DesenNod();
      return right;
   }

   void setRadacina(Nod r)                       // seteaza radacina
   {
      radacina = r;
   }

   Nod getRadacina()                             // returneaza radacina
   {
      return radacina;
   }

   void setParinte (Arbore Arb)                  // seteaza parintele
   {
      parinte = Arb;
   }

   Arbore getParinte()                           // citeste parintele
   {
      return parinte;
   }

   void setLeft(Arbore Arb)                      // Adauga un subarbore stang
   { 
      left = Arb;
   }

   Arbore getLeft()                              // returneaza arborele stang
   {
      return left;
   }

   void setRight(Arbore Arb)                     // Adauga un subarbore drept
   { 
      right= Arb;
   }

   Arbore getRight()                             // returneaza arborele drept            
   {
      return right;
   }

   void setCentru(int i)                         // seteaza centru pentru nodul curent
   {
      centru+= i;
   }

   void resetCentru (int i)                      // reseteaza centrul dedesenare al nodului curent 
   {
      centru= i;
   }

   int getCentru()                               // returnaeza centrul de desenare
   {
      return centru;
   }

   void setLeftCentru(int i)                     // seteaza centrul fiului din stanga
   {
      leftCentru+= i;
   }

   void resetLeftCentru(int i)                   // reseteaza centrul fiului din stanga
   {
      leftCentru= i;
   }

   int getLeftCentru()                           // returneaza centrul fiului din stanga
   {
      return leftCentru;
   }

   void setRightCentru(int i)                    // seteaza centrul fiului din dreapta
   {
      rightCentru += i;
   }

   void resetRightCentru(int i)                  // reseteaza centrul fiului din dreapta
   {
      rightCentru = i;
   }

   int getRightCentru()                          // returneaza centrul fiului din dreapta
   {
      return rightCentru;
   }

   boolean neEgal(Nod elem)                      // testeaza inegalitatea
   {
      return radacina!=elem ? true : false;
   }
   
   Arbore Creare (int nrVar1, String expr, int directie, Arbore Arb, ExprLogic e)
   {
   	String str1;
   	String val;
   	boolean rad;
   	Arbore Arb1 = new Arbore();
   	Nod n;
   	int nrVar = nrVar1;   
   //	System.out.println("////-----------------"+nrVar1+"         "+expr);

   	
   	val =new String(e.evalExpr(nrVar, expr));                // se testeaza dependenta expresiei de variabile
 	
 	rad = false;
   	if ( val.compareTo("1")==0 || val.compareTo("0")==0 )
   		if (directie == 1)                        // daca directie 1 se adauga in stanga altfel in dreapta
   		    { 
   	  	      n = new Nod(1,val);
   	  	      if (Arb.radacina == null)
   	  	         { Arb = new Arbore(n);Arb.setParinte(Arb);rad =true;}
   	  	      else   
   	  	      	 { Arb.nouLeft(n); }
   	  	      return Arb.getParinte();
   	  	     }
   	  	else
		     { 
   	  	      n = new Nod(1,val);
			  if (Arb.radacina == null)
   	  	         {Arb = new Arbore(n);Arb.setParinte(Arb);rad =true;}
   	  	      else   
   	  	         {Arb.nouRight(n);}
   	  	      return Arb.getParinte();
   	  	     }   	  	          
   	else
   	    {
   	      n = new Nod(0,val);
   	      if (Arb.radacina == null)
   	    	  { Arb = new Arbore(n);
   	    	    rad =true;
   	    	   Arb.setParinte(Arb);
   	    	  } 
   	      else 
   	         if ( directie == 1 )
   	    	  {  
   	    	    Arb.nouLeft(n); 	    	    
   	    	   }
   	    	 else 
   	    	   {  
   	    	    Arb.nouRight(n);
   	    	    
   	    	   } 
   	    	    
   	    	    str1 = expr;
   	    		while (str1.compareTo(expr)==0)
   	    		  {
   	    		  	str1 = e.elimVarPeLow(nrVar,expr);
   	    		  	nrVar++;
   	    		  	
   	              }
   	              nrVar--;
   	            if (rad)
   	               Creare(nrVar1+1, str1, 1, Arb,e);
   	            else   
   	            	if (directie == 1 )
   	            		Creare(nrVar1+1, str1, 1, Arb.getLeft(),e);
   	            	else
   	            		{ Creare(nrVar1+1, str1, 1, Arb.getRight(),e);}
				
				str1 = expr;
   	    		while (str1.compareTo(expr)==0)
   	    		  {
   	    		  	str1 = e.elimVarPeHigh(nrVar,expr);
   	    		  	nrVar++;
   	    		  	
   	              }
   	              nrVar--;	
				
				if (rad)	
   	              { Creare(nrVar1+1, str1, 0, Arb,e);}
   	            else   
   	               	              
   			        if (directie == 1 )
   	            	     { Creare(nrVar1+1, str1, 0, Arb.getLeft(),e); }
   	                else
   	            	     Creare(nrVar1+1, str1, 0, Arb.getRight(),e); return Arb.getParinte();
   	  
   	   }
   	   
   	   
   	    
}   	    
   	    	
   		
void nrNodStanga (int n, Arbore Arb, int [] nrNod)
{
	int n1=0,n2=0;

	if (n == 0)
		nrNod[n] = 1;
	
	if (Arb.getLeft()!=null)
	   { 
	     nrNod[n+1] ++;	    
	     nrNodStanga(n+1,Arb.getLeft(),nrNod);
	   }
	
	if (Arb.getRight()!=null && n!=0)
	   {
	   	nrNod[n+1]++;
	   	nrNodStanga(n+1,Arb.getRight(),nrNod);
	   	}
	
}   	
   	

void nrNodDreapta (int n, Arbore Arb, int [] nrNod)
{
	int n1=0,n2=0;
	
	if (n == 0)
		nrNod[n] = 0;
	
	if (Arb.getLeft()!=null&& n!=0)
	   { 
	     nrNod[n+1] ++;	    
	     nrNodDreapta(n+1,Arb.getLeft(),nrNod);
	   }
	
	if (Arb.getRight()!=null )
	   {
	   	nrNod[n+1]++;
	   	nrNodDreapta(n+1,Arb.getRight(),nrNod);
	   	}
}   	
  

void nrIntorcDirST (int n, Arbore Arb, int [] nrNod, int dir)   // numarul de intoarceri spre stanga
{
		
	if (dir == 1)	                                       // stanga
	  { 
	    if (Arb.getRight()!=null)	       
	        { nrIntorcDirST(n+1,Arb.getRight(),nrNod,0);
	          nrIntorcDirST(n+1,Arb.getRight(),nrNod,1); 
	        }  
	    else
	        return;
	   }
	else
	  { if (Arb.getLeft()!=null)
	       { nrNod[n]++;
	         nrIntorcDirST(n,Arb.getLeft(),nrNod,0);
	       }
	    else
	       return;
	  }
}	                        
	
void nrIntorcDirDr (int n, Arbore Arb, int [] nrNod, int dir)
{
		
	if (dir == 1)	                                       // stanga
	  { 
	    if (Arb.getLeft()!=null)	       
	        { 
	          nrIntorcDirDr(n+1,Arb.getLeft(),nrNod,0);
	          nrIntorcDirDr(n+1,Arb.getLeft(),nrNod,1); 
	        }  
	    else
	        return;
	   }
	else
	  { if (Arb.getRight()!=null)
	       { nrNod[n]++;
	         nrIntorcDirDr(n,Arb.getRight(),nrNod,0);
	       }
	    else
	       return;
	  }
}


void setDreapta(Arbore Arb)
{ 
  int []nrNod = new int[30];
            
      
  if (Arb != null)
 	{	setDreapta(Arb.getLeft());
        setDreapta(Arb.getRight());}
  else 
   return;
   	
   	 for(int i=0; i<30; i++)
      nrNod[i] = 0;
     
     Arb.nrIntorcDirDr(0,Arb, nrNod, 1);
     
     int max = nrNod[0];
     
     for (int i=1; i<30; i++)
          if (max < nrNod[i])
             max = nrNod[i];     
     if (Arb.getLeft()!= null)
        Arb.radacina.pozX1 = max+Arb.getLeft().radacina.pozX1;   

     
}       

void setStanga(Arbore Arb)
{ 
  int []nrNod = new int[30];
            
      
  if (Arb != null)
 	{	setDreapta(Arb.getLeft());
        setDreapta(Arb.getRight());}
  else 
   return;
   	
   	 for(int i=0; i<30; i++)
      nrNod[i] = 0;
     
     Arb.nrIntorcDirST(0,Arb, nrNod, 1);
     
     int max = nrNod[0];
     
     for (int i=1; i<30; i++)
          if (max < nrNod[i])
             max = nrNod[i];     
     if (Arb.getRight()!= null)
        Arb.radacina.pozX2 = max+Arb.getRight().radacina.pozX2;   

     
}       
void SetDreapta(Arbore Arb)
{ 
   if (Arb.getLeft()!=null)
       SetDreapta(Arb.getLeft());
   if (Arb.getRight()!=null)
       SetDreapta(Arb.getRight());
	if (Arb == null) 
     return;
    else 
     { if (Arb.getRight() !=null)
         Arb.radacina.pozX1 +=Arb.getRight().radacina.pozX1;
       return;
     }    
}
void stabilCoord(Graphics g,Arbore Arb,int dis, int raza, int startX, int startY, int directie, int nr)	              
{
	int [] nrNod = new int[30];
	int max;
	int disY = 70;
	for (int i = 0; i<30; i++)
	  nrNod[i]=0;

	if (Arb == Arb.getParinte() && Arb!= null)
	     {
			Arb.radacina.pozX = startX;
			Arb.radacina.pozY = startY;
			Arb.nrIntorcDirDr (0,Arb,nrNod,1);			
			max = nrNod[0];	
		    
		for (int i=1; i<30; i++)
          if (max < nrNod[i])
             max = nrNod[i];
			if (Arb.getLeft() != null)       
		    	{  max+= Arb.radacina.pozX1;
		    		stabilCoord(g,Arb.getLeft(),dis,raza,startX,startY+disY,1,0);		    
		    }
		    for (int i = 0; i<30; i++)
	  			nrNod[i]=0;

			nrIntorcDirST (0,Arb,nrNod,1);			
			max = nrNod[0];	
		    for (int i=1; i<30; i++)
                if (max < nrNod[i])
                    max = nrNod[i];
			if (Arb.getRight() != null)     
			   {
			   	 max+= Arb.radacina.pozX1;	  			
		    	stabilCoord(g,Arb.getRight(),dis,raza,startX,startY+disY,0,max);
		    }
		    else
		        return;	
		 }
	else
		 { 
		   if (directie == 1)
		       {
		    	Arb.radacina.pozX = startX-(nr+1)*(dis+raza);
				Arb.radacina.pozY = startY;
			    } 
		   else
		       {
		       	Arb.radacina.pozX = startX+(nr+1)*(dis+raza);
				Arb.radacina.pozY = startY;
			   }
	            Arb.nrIntorcDirDr (0,Arb,nrNod,1);			
			    max = nrNod[0];	
			
			    for (int i=1; i<30; i++)
                    if (max < nrNod[i])
                         max = nrNod[i];
			            
			    if (Arb.getLeft() != null)     
		        	{max+= Arb.radacina.pozX1;
		        
		        		stabilCoord(g,Arb.getLeft(),dis,raza,Arb.radacina.pozX,startY+disY,1,0);
		             }
				for (int i = 0; i<30; i++)
	  			    nrNod[i]=0;

				Arb.nrIntorcDirST (0,Arb,nrNod,1);			
				max = nrNod[0];	
			
			    for (int i=1; i<30; i++)
                    if (max < nrNod[i])
                         max = nrNod[i];
			            
			    if (Arb.getRight() != null)   	  			
		    	   { max+= Arb.radacina.pozX1;
		    	   	stabilCoord(g,Arb.getRight(),dis,raza,Arb.radacina.pozX,startY+disY,0,max);
		    	   }	
		    	else
		    	   return;	
		  }
		       
		  
           
		       
}

int nrNivel(Arbore Arb)
{ 
  int max1,max2;
    if (Arb == null)
         return 0;
    else
       { max1 = nrNivel(Arb.getLeft());
         max2 = nrNivel(Arb.getRight());
         if (max1>max2)
            return 1+max1;
         else
            return 1+max2;
       }
}                    
    
void desenBinar(Arbore Arb, int nrNive, int startX, int startY,int raza, int dis, int disY,int directie)
{   int rez=1, rez1=0;
   	if (Arb == Arb.getParinte() && Arb!= null)
	     {
			Arb.radacina.pozX = startX;
			Arb.radacina.pozY = startY;
        }
        
    else
         { for (int i=1;i<nrNive;i++)
               
               rez *= 2 ; 
                
            if ( directie == 1 )
		     	Arb.radacina.pozX = startX-rez*(raza+dis);
		    else 
		        Arb.radacina.pozX = startX+rez*(raza+dis); 	
			Arb.radacina.pozY = startY;
        }    
      
    if (Arb.getLeft() != null )
        desenBinar(Arb.getLeft(),nrNivel(Arb.getLeft()),Arb.radacina.pozX,startY+disY,raza,dis,disY,1);
    if (Arb.getRight() != null )
        desenBinar(Arb.getRight(),nrNivel(Arb.getRight()),Arb.radacina.pozX,startY+disY,raza,dis,disY,0);    
               
      
}      





void desenBinar1(Arbore Arb, int nrNive, int startX, int startY,int raza, int dis, int disY,int directie)
{   
    Arbore next = null;
    int rez=1, rez1=0,max=0,niv=0;
    int []nrNod = new int[30];
    // System.out.println("max : "+ max+ "niv : "+niv);   
   	if (Arb == Arb.getParinte() && Arb!= null)
	     {
			Arb.radacina.pozX = startX;
			Arb.radacina.pozY = startY;
        }
        
    else
         { for (int i=1;i<nrNive;i++)
               
               rez *= 2 ; 
                
            if ( directie == 1 )
		     	Arb.radacina.pozX = startX-rez*(raza+dis);
		    else 
		        Arb.radacina.pozX = startX+rez*(raza+dis); 	
			Arb.radacina.pozY = startY;
        }    
      
    if (Arb.getLeft() != null )
        { 
          
          for (int i = 0;i <30; i++)
              nrNod[i] = 0;
          
          nrIntorcDirDr (0, Arb, nrNod, 1);
          
          max = nrNod[0];
          
          for (int i = 1;i <30; i++)
              if (max < nrNod[i]-i)
                   max = nrNod[i]-i;
          niv = nrNivel(Arb.getLeft());            
          System.out.println("max : "+ max+ "niv : "+niv);
          max=max+2;
          if (max<=niv)           
              desenBinar1(Arb.getLeft(),max,Arb.radacina.pozX,startY+disY,raza,dis,disY,1);
          else 
              desenBinar1(Arb.getLeft(),niv,Arb.radacina.pozX,startY+disY,raza,dis,disY,1); 
    }
        
    if (Arb.getRight() != null )
       {
       	
       	for (int i = 0;i <30; i++)
              nrNod[i] = 0;
          nrIntorcDirST (0, Arb, nrNod, 1);
          
          max = nrNod[0];
          
          for (int i = 1;i <30; i++)
              if (max < nrNod[i]-i)
                   max = nrNod[i]-i;
          niv = nrNivel(Arb.getRight());    
       	System.out.println("max : "+ max+ "niv : "+niv);
       	max=max+2;
       	 if (max<=niv)   
       	    desenBinar1(Arb.getRight(),max,Arb.radacina.pozX,startY+disY,raza,dis,disY,0);    
       	 else 
       	    desenBinar1(Arb.getRight(),niv,Arb.radacina.pozX,startY+disY,raza,dis,disY,0);    
        }       
      
}      

void DesenArbore(Graphics g, Arbore Arb,int raza,int transX, int transY)
 { Arbore next;
   String s="";
   if (Arb == null)
      return;
   else
      {  if (Arb.radacina.Valoare.compareTo("1")== 0 || Arb.radacina.Valoare.compareTo("0") == 0) 
           {
         	 g.setColor(new Color(150,150,250));
         	 g.fillRect(Arb.radacina.pozX+transX-raza,Arb.radacina.pozY+transY-raza,2*raza,2*raza);
		  	 g.setColor(Color.yellow);		  	 
      	     g.drawRect(Arb.radacina.pozX+transX-raza,Arb.radacina.pozY+transY-raza,2*raza,2*raza);
      	     g.setColor(Color.black);   
      	     g.drawString(Arb.radacina.Valoare,Arb.radacina.pozX+transX-raza+raza/2, Arb.radacina.pozY+transY+raza/2);
         	}
         else	 
         	{g.setColor(new Color(250,200,100));
         	 g.fillOval(Arb.radacina.pozX+transX-raza,Arb.radacina.pozY+transY-raza,2*raza,2*raza);
		  	 //g.setColor(Color.yellow);
      	    // g.drawOval(Arb.radacina.pozX+transX-raza,Arb.radacina.pozY+transY-raza,2*raza,2*raza);   
      	     g.setColor(Color.black); 
      	     g.drawString(Arb.radacina.Valoare,Arb.radacina.pozX+transX-raza+raza/2, Arb.radacina.pozY+transY+raza/2);
            }
      	  if (Arb.getLeft()!=null)
      	     {
      	     	next = Arb.getLeft();
      	        g.setColor(Color.red);
      	     	g.drawLine(Arb.radacina.pozX+transX-4,Arb.radacina.pozY+transY+raza,next.radacina.pozX+transX+4,next.radacina.pozY+transY-raza);
      	     }	
      	  if (Arb.getRight()!=null)
      	     {
      	     	next = Arb.getRight();
      	        g.setColor(Color.blue);
      	     	g.drawLine(Arb.radacina.pozX+transX+4,Arb.radacina.pozY+transY+raza,next.radacina.pozX+transX-4,next.radacina.pozY+transY-raza);
      	     }	
      	     
      	  DesenArbore(g,Arb.getLeft(),raza,transX,transY);
      	  DesenArbore(g,Arb.getRight(),raza,transX,transY);
      }
      //for (int i=0;i<1200/(raza))
 }     	  

}