import java.awt.*;  
/**Operationen an einem Binaerbaum
*/
public final class BBTools{

	/**Bestimmung der Knotenanzahl
	*/	
 public static int knotenzahl (Baum b){
   if(b == null)return 0;
	 else return 1 + knotenzahl(b.linkerBaum())+ knotenzahl(b.rechterBaum());
 }
	/**Bestimmung des größten Elementes, indem jeweils im rechten Baum, nach rechts
  		gegangen wird, und falls rechter Baum irgendwann mal Null sein sollte Wurzel-
  		element zurueckgegeben wird.
	*/
  public static Object ganzRechts(Baum b){
  	 if (b == null) return null;
		else if (b.rechterBaum() == null) return b.liesWurzel();
		 else return ganzRechts(b.rechterBaum());
	}
	
	/**Bestimmung des größten Elementes, indem jeweils im linken Baum, nach links
  		gegangen wird, und falls linker Baum irgendwann mal Null sein sollte Wurzel-
  		element zurueckgegeben wird.
	*/	
	public static Object ganzLinks(Baum b){
	 if (b == null) return null;
		else if (b.linkerBaum() == null) return b.liesWurzel();
		 else return ganzLinks(b.linkerBaum());
	}
	
	/**Ausgabe des Baumes indem je nach Tiefe die Verzweigungen immer enger zueinander
		gemalt werden.
		Wurzelelemente werden ausgegeben und Verbindungslinien.
		Aufruf rekursiv mit kleineren Verbindungslinien für linken bzw. rechten Baum
	*/
	public static void zeichnen(Graphics g, Baum b, int l, int r, int t) {
	  g.setFont(new Font("Serif", Font.PLAIN, 14));
	  if (b != null){
	  String s = (String) b.liesWurzel();
		int x = (int) ((l+r - s.length()*7) / 2);
		g.setColor(Color.yellow);
		g.drawString(s, x, t*36);
		int x1 = (int) ( (l+r)/2);
		int y1 = t*36 + 7;
		int x2 = (int) ((l+x1)/2);
		int x3 = (int) ((x1+r)/2);
		int y2 = y1 + 36;
		g.setColor(Color.red);
		if (b.linkerBaum() != null) g.drawLine(x1, y1, x2, y2);
		 else g.fillOval(x1-3, y1-3, 6, 6);
		if (b.rechterBaum() != null) g.drawLine(x1, y1, x3, y2);
		 else g.fillOval(x1-3, y1-3, 6, 6);
	  zeichnen(g, b.linkerBaum(),  l, (int)(l+r)/2, t+1);
	  zeichnen(g, b.rechterBaum(),  (int) (l+r)/2, r, t+1);
	 }
	}

	/**Ausgabe des Baumes falls Suchvorgang gestartet wurde, da der Weg zum zu suchendem
		Element markiert wird. Ansonsten genauso wie nornmale Ausgabe zeichnen.
	*/	
	public static void zeichnen2(Graphics g, Baum b, int l, int r, int t,String such) {
		if(such=="" )	zeichnen(g, b,l,r,t);
		else{
	 	 	g.setFont(new Font("Serif", Font.PLAIN, 14));
	  		if (b != null){
	  			String s = (String) b.liesWurzel();
	  		  	int x = (int) ((l+r - s.length()*7) / 2);
				g.setColor(Color.yellow);
				g.drawString(s, x, t*36);
				int x1 = (int) ( (l+r)/2);
				int y1 = t*36 + 7;
				int x2 = (int) ((l+x1)/2);
				int x3 = (int) ((x1+r)/2);
				int y2 = y1 + 36;
				if( Integer.valueOf(such).intValue() == Integer.valueOf(s).intValue() ){
					g.setColor(Color.black);
					g.drawString(s, x, t*36);
					g.setColor(Color.red);
					if (b.linkerBaum() != null) g.drawLine(x1, y1, x2, y2);
		 			else g.fillOval(x1-3, y1-3, 6, 6);
					if (b.rechterBaum() != null) g.drawLine(x1, y1, x3, y2);
		 			else g.fillOval(x1-3, y1-3, 6, 6);
					zeichnen(g, b.linkerBaum(),  l, (int)(l+r)/2, t+1);
	  				zeichnen(g, b.rechterBaum(),  (int) (l+r)/2, r, t+1);
				}
				else{
					if( Integer.valueOf(such).intValue() < Integer.valueOf(s).intValue() ){
						g.setColor(Color.yellow);
						if (b.linkerBaum() != null) g.drawLine(x1, y1, x2, y2);
			 			else g.fillOval(x1-3, y1-3, 6, 6);
			 		 	g.setColor(Color.red);
						if (b.rechterBaum() != null) g.drawLine(x1, y1, x3, y2);
			  			zeichnen2(g, b.linkerBaum(),  l, (int)(l+r)/2, t+1,such);
			 			zeichnen(g, b.rechterBaum(),  (int) (l+r)/2, r, t+1);
			 		}
			 		else{
				 		g.setColor(Color.yellow);
						if (b.rechterBaum() != null) g.drawLine(x1, y1, x3, y2);
			 			else g.fillOval(x1-3, y1-3, 6, 6);
			 			g.setColor(Color.red);
			 	 		if (b.linkerBaum() != null) g.drawLine(x1, y1, x2, y2);
			  			zeichnen2(g, b.rechterBaum(),  (int) (l+r)/2, r, t+1,such);
			 			zeichnen(g, b.linkerBaum(),  l, (int)(l+r)/2, t+1);
					}
				}		 	  
	 		}
	 	}
	}
	
}//BBTools