import java.awt.*;

public class BinBaum {
protected Ordnung ord;
protected Baum b;
	/**Konstruktor, leerer Baum mit Ordnung
	*/
	public BinBaum(Ordnung og) {							
		b = null;
		ord = og;
	}
	/**Binaerbaum wird zurückgegeben
	*/	
	public Baum liefereBinBaum(){
	  return b;
	}
	/**leerer Binaerbaum wird zurückgegeben
	*/
	public boolean istLeer(){
		  return b == null;
	}
	/**Einfuegevorgang des Elementes, indem zuerst Element mit dem jeweiligen Wurzelelement
		verglichen wird, und dann je nach Ordnung links oder rechts verzweigt wird und insert 
		mit dem linken oder rechten Baum aufgerufen wird.
		Falls linker oder rechter Baum dann einmal Null sein sollte wird Element drangehangen.	
	*/
	public Baum insert(Baum bb, Object obj){
			if(bb != null){ 
			Object wurzel = bb.liesWurzel();
			int vergleichszahl = ord.ordnung(obj, wurzel);
			if(vergleichszahl < 0){
				try {
        			Thread.sleep(400);
	   			} catch (InterruptedException e) {}
	   			Pseudocode.tar.append("if (Wurzel < Element) return new Baum");
	   			Pseudocode.tar.append("(insert(b.linkerBaum(),obj),wurzel,b.rechterBaum());\n");
				return new Baum(insert(bb.linkerBaum(), obj), wurzel,bb.rechterBaum());
			}
			else if(vergleichszahl >0){
				try {		   								
			   	Thread.sleep(400);
	    		} catch (InterruptedException e) {}
	    		Pseudocode.tar.append("if (Wurzel > Element) return new Baum");
	    		Pseudocode.tar.append("(b.linkerBaum(),wurzel,insert(b.rechterBaum(),obj));\n");
				return  new Baum(bb.linkerBaum(),wurzel,insert(bb.rechterBaum(), obj));
			}
			else{
				try {
				Thread.sleep(400);
		    	} catch (InterruptedException e) {}
		    	Pseudocode.tar.append("else return Baum;\n");		
				return bb;
			}
		}
		else{								  					// bb == null
			try {
			Thread.sleep(400);
	    	} catch (InterruptedException e) {}
	    	Pseudocode.tar.append("if (Baum == null) return new Baum(obj);\n");	
		    return new Baum(obj);
		}
	}	
	/**neuer Binaerbaum wird geschaffen, und mit aktuellem Element und dem Baum
	 in Funktion insert gegangen
	*/	
	public BinBaum einfuegen(Object obj){
	 Pseudocode.tar.setText("");
	 BinBaum s = new BinBaum (ord);
	 s.b = insert(b, obj);
	 return s;
	}

/**Löschvorgang des Elementes, indem zuerst Element mit dem jeweiligen Wurzelelement
		verglichen wird, und dann je nach Ordnung links oder rechts verzweigt wird und delete 
		mit dem linken oder rechten Baum aufgerufen wird.
		Falls Element dann gefunden ist wird untersucht ob rechter Baum Null ist, dann wird 
		einfach linker Baum zurückgegeben.
		Falls linker Baum Null ist, dann wird genauso rechter Baum zurückgegeben.
		Ansonsten wenn beide ungleich Null sind wird minimales Element vom rechten Baum gesucht,
		dies zur Wurzel gemacht und aus alter Position geloescht.
*/
public Baum delete(Baum bb, Object obj){
		if(bb == null){
			try {
			Thread.sleep(400);
	   		} catch (InterruptedException e) {}
	   		Pseudocode.tar.append("if (Baum == null) return null;\n");														//bb == null
			return null;
		}
		else { 
			Object wurzel = bb.liesWurzel();
			int vergleichszahl = ord.ordnung(obj, wurzel);
			if(vergleichszahl < 0) { 								//obj < wurzel
				try {
       			Thread.sleep(400);
	   			} catch (InterruptedException e) {}
	   			Pseudocode.tar.append("if (Wurzel < Element) return new Baum");
	   			Pseudocode.tar.append("(delete(b.linkerBaum(),obj),wurzel,b.rechterBaum());\n");
				return new Baum(delete(bb.linkerBaum(), obj),wurzel,bb.rechterBaum());
			}
			else if(vergleichszahl >0){							//obj > wurzel
				try {		   								
			   	Thread.sleep(400);
	   			} catch (InterruptedException e) {}
	   			Pseudocode.tar.append("if (Wurzel > Element) return new Baum");
	   			Pseudocode.tar.append("(b.linkerBaum(),wurzel,delete(b.rechterBaum(),obj));\n");
				return  new Baum(bb.linkerBaum(),wurzel,delete(bb.rechterBaum(), obj));
			}	
			else if(bb.rechterBaum() == null){				//obj == wurzel, rechts = null
				try {
				Thread.sleep(400);
	   			} catch (InterruptedException e) {}
	   			Pseudocode.tar.append("if (rechterBaum == null) return linkerBaum;\n");		
				return bb.linkerBaum();
			}
			else if(bb.linkerBaum() == null){
				try {
				Thread.sleep(400);
	  			} catch (InterruptedException e) {}
	   			Pseudocode.tar.append("if (linkerBaum == null) return rechterBaum;\n");		
			  	return bb.rechterBaum();
			}		
			else {
			  	Object minRechts = BBTools.ganzLinks(bb.rechterBaum());
			  	try {
				Thread.sleep(400);
	   			} catch (InterruptedException e) {}
	   			Pseudocode.tar.append("else return Baum(b.linkerBaum(),minRechts,");
	   			Pseudocode.tar.append("delete(b.rechterBaum(),minRechts));\n");	
			  	return new Baum (bb.linkerBaum(),minRechts,delete(bb.rechterBaum(), minRechts));
			}
		}
	}	//Delete
	/**neuer Binaerbaum wird geschaffen, und mit aktuellem Element und dem Baum
	 in Funktion delete gegangen
	*/	
	public BinBaum loeschen(Object obj){
	 Pseudocode.tar.setText("");
	 BinBaum s = new BinBaum (ord);
	 s.b = delete(b, obj);
	 return s;
	}
/**Suchvorgang des Elementes, indem zuerst Element mit dem jeweiligen Wurzelelement
		verglichen wird, und dann je nach Ordnung links oder rechts verzweigt wird und search 
		mit dem linken oder rechten Baum aufgerufen wird.
		Abbruch falls Wurzelelement dann einmal gleich dem gesuchten Element ist, oder Element
		nicht enthalten (linker bzw. rechter Baum Null ist.
*/
public Baum search(Baum b, Object obj){
		if(b == null){										//bb == null
			try {
			Thread.sleep(400);
	   		} catch (InterruptedException e) {}
	   		Pseudocode.tar.append("if (Baum == null) return null;\n");	//Algorithmusausgabe
			return null;
		}
		else { 
			Object wurzel = b.liesWurzel();
			int vergleichszahl = ord.ordnung(obj, wurzel);
			if (vergleichszahl == 0){							//obj == wurzel
				try {
        			Thread.sleep(400);
	   			} catch (InterruptedException e) {}
	   			Pseudocode.tar.append("if (Wurzel == Element) return Baum;\n");
 				return b;
			}
			else{
				if(vergleichszahl < 0)  {						//obj < wurzel
					try {
        				Thread.sleep(400);
	   				} catch (InterruptedException e) {}
	   				Pseudocode.tar.append("if (Wurzel < Element) return new Baum");
	   				Pseudocode.tar.append("(search(b.linkerBaum(),obj),wurzel,b.rechterBaum());\n");
					return new Baum(search(b.linkerBaum(), obj),wurzel,b.rechterBaum());
				}
				else{											//obj > wurzel
					try {		   								
				  		Thread.sleep(400);
	    			} catch (InterruptedException e) {}
	    			Pseudocode.tar.append("if (Wurzel > Element) return new Baum");
	    			Pseudocode.tar.append("(b.linkerBaum(),wurzel,search(b.rechterBaum(),obj));\n");
					return  new Baum(b.linkerBaum(),wurzel,search(b.rechterBaum(), obj));
				}
			}
		}
}	//Suchen

	/**neuer Binaerbaum wird geschaffen, und mit aktuellem Element und dem Baum
	 in Funktion search gegangen
	*/
	public BinBaum suchen(Object obj){
		Pseudocode.tar.setText("");
	 	BinBaum s = new BinBaum (ord);
		s.b = search(b, obj);
		return s;
	}
/**Ausgleichvorgang indem linker und rechter Baum auf Knotenanzahl untersucht wird,
	und je nach Anzahl im linken bzw. rechten Baum nach kleinsten bzw. größtenm Element
	gesucht wird.
	Danach wird Baum "umgehangen" kleinste bzw. größtes Element wird zur Wurzel gemacht,
	und baum erneut zum ausgleichen gebracht, solange bis irgendwann Knotenanzahl sich nur
	um eins unterscheiden.
*/	
public Baum ausgleich(Baum bb){
		if(bb == null){											//bb == null
			try {
        		Thread.sleep(200);
	    	} catch (InterruptedException e) {}
	    	Pseudocode.tar.append("if (Baum == null) return null;\n");
			return null;
		}
		else { 
			Object wurzel = bb.liesWurzel();
			if(BBTools.knotenzahl(bb.linkerBaum())+1 < BBTools.knotenzahl(bb.rechterBaum()) ){
				Object r = BBTools.ganzLinks(bb.rechterBaum());			
				return ausgleich(new Baum(insert(bb.linkerBaum(),wurzel),r,delete(bb.rechterBaum(),r)));
			}
			else if(BBTools.knotenzahl(bb.linkerBaum())-1 > BBTools.knotenzahl(bb.rechterBaum()) ){
				Object r = BBTools.ganzRechts(bb.linkerBaum());			
				return ausgleich(new Baum(delete(bb.linkerBaum(),r),r,insert(bb.rechterBaum(),wurzel)));
			}
			else return new Baum(ausgleich(bb.linkerBaum()),wurzel,ausgleich(bb.rechterBaum()));
		} //else
}	//ausgleich

	/**neuer Binaerbaum wird geschaffen, und mit dem Baum
	 in Funktion insert gegangen
	*/	
	public BinBaum ausgleichen(){
		Pseudocode.tar.setText("");
		BinBaum s = new BinBaum (ord);
	 	s.b = ausgleich(b);
	 	return s;
	}
	
/**Preorder-Durchlauf des Baumes, indem in einen String immer zuerst die
		Wurzel, dann der linke Baum mit Preorder-Durchlauf und dann der
		rechte Baum mit Preorder-Durchlauf die Elemente eingefügt werden.
		Danach Ausgabe des Strings.
*/
public String preor(Baum b){
	String rueckgabe = "";
    try {
         Thread.sleep(500);
	} catch (InterruptedException e) {}
    Pseudocode.tar.append("Wurzel einlesen\n");
    rueckgabe = rueckgabe + b.liesWurzel() + " ";
    if (b.linkerBaum() != null){
    	try {
         Thread.sleep(500);
	    } catch (InterruptedException e) {}
    	Pseudocode.tar.append("if (linkerBaum != 0) preor(b.linkerBaum())\n");
    	rueckgabe = rueckgabe + preor(b.linkerBaum());
  	}
    if  (b.rechterBaum() != null){
    	try {
         Thread.sleep(500);
	    } catch (InterruptedException e) {}
	   	Pseudocode.tar.append("if rechterBaum != 0 preor(b.rechterBaum())\n");
    	rueckgabe = rueckgabe + preor(b.rechterBaum());
  	}
    return rueckgabe;
}

/**neuer Binaerbaum wird geschaffen, und mit aktuellem Element 
 in Funktion preor gegangen
 Ausgabe des Durchlaufes
 alter Binaerbaum wird einfach zurückgegeben
*/
public BinBaum preorder(){
	Pseudocode.tar.setText("");
	BinBaum s = new BinBaum (ord);
	if(b==null) return s;
	else{
		String pr=preor(b);
		Pseudocode.tar.append(pr);
		s.b = b;
		return s;
	}
}

/**Postorder-Durchlauf des Baumes, indem in einen String immer zuerst der
	linke Baum mit Postorder-Durchlauf,der rechte Baum mit Postorder-Durchlauf
	und dann die Wurzel, die Elemente eingefügt werden.
	Danach Ausgabe des Strings.
*/
public String postor(Baum b){
    String rueckgabe = "";
    if (b.linkerBaum() != null){
    	try {
         Thread.sleep(500);
	    } catch (InterruptedException e) {}
    	Pseudocode.tar.append("if (linkerBaum != 0) postor(b.linkerBaum())\n");
      	rueckgabe = rueckgabe + postor(b.linkerBaum());
    }
    if (b.rechterBaum() != null){
    	try {
         Thread.sleep(500);
	    } catch (InterruptedException e) {}
	   	Pseudocode.tar.append("if rechterBaum != 0 postor(b.rechterBaum())\n");
      	rueckgabe = rueckgabe + postor(b.rechterBaum());
    }
    try {
         Thread.sleep(500);
	    } catch (InterruptedException e) {}
    Pseudocode.tar.append("Wurzel einlesen\n");
    rueckgabe = rueckgabe + b.liesWurzel() + " ";
    return rueckgabe;

}	
	/**neuer Binaerbaum wird geschaffen, und mit aktuellem Element 
	 in Funktion postor gegangen
	 Ausgabe des Durchlaufes
	 alter Binaerbaum wird einfach zurückgegeben
	*/
	public BinBaum postorder(){
		Pseudocode.tar.setText("");
		BinBaum s = new BinBaum (ord);
		if(b==null) return s;
		else{
			String po=postor(b);
			Pseudocode.tar.append(po);
	 		s.b = b;
	 		return s;
	 	}
	}

/**Inorder-Durchlauf des Baumes, indem in einen String immer zuerst der
	linke Baum mit Inorder-Durchlauf, die Wurzel und dann der
	rechte Baum mit Inorder-Durchlauf die Elemente eingefügt werden.
	Danach Ausgabe des Strings.
*/
public String inor(Baum b){
	String rueckgabe = "";
    if (b.linkerBaum() != null){
    	try {
        Thread.sleep(500);
	    } catch (InterruptedException e) {}
    	Pseudocode.tar.append("if (linkerBaum != 0) inor(b.linkerBaum())\n");
      	rueckgabe = rueckgabe + inor(b.linkerBaum());
  	}
  	try {
         Thread.sleep(500);
	    } catch (InterruptedException e) {}
    Pseudocode.tar.append("Wurzel einlesen\n");
    rueckgabe = rueckgabe + b.liesWurzel() + " ";
    if  (b.rechterBaum() != null){
    	try {
         Thread.sleep(500);
	    } catch (InterruptedException e) {}
	   	Pseudocode.tar.append("if rechterBaum != 0 inor(b.rechterBaum())\n");
      	rueckgabe = rueckgabe + inor(b.rechterBaum());
  	}
    return rueckgabe;
}	

	/**neuer Binaerbaum wird geschaffen, und mit aktuellem Element 
	 in Funktion inor gegangen
	 Ausgabe des Durchlaufes
	 alter Binaerbaum wird einfach zurückgegeben
	*/
	public BinBaum inorder(){
		Pseudocode.tar.setText("");
		BinBaum s = new BinBaum (ord);
		if(b==null) return s;
		else{
			String in=inor(b);
			Pseudocode.tar.append(in);
			s.b=b;
	 		return s;
	 	}
	}

}// BinBaum