/*******************************************************************/
/* Prof. Dr. Carsten Vogt                                          */
/* FH Koeln, Fak. 07 / Nachrichtentechnik                          */
/* http://www.nt.fh-koeln.de/vogt                                  */
/*                                                                 */
/* Das Programm definiert eine Klasse fuer Knoten von Binaerbaeume */
/* sowie Methoden zur Ein- und Ausgabe von Binaerbaeumen.          */
/*                                                                 */
/* ANMERKUNG: Aus unbekanntem Grund lässt sich das Programm aus    */
/* dem Java-Editor heraus nicht ausführen - beim readLine()-Aufruf */
/* kommt es zu einer Fehlermeldung. Ruft man das Programm von der  */
/* DOS-Oberflaeche auf, laeuft es einwandfrei.                     */
/*                                                                 */
/*******************************************************************/

import java.io.*;
import java.util.*;
import java.awt.*;
import javax.swing.*;


/****************************************************************

   Die Klasse 'Binaerknoten' definiert Knoten in Binaerbaeumen.
   
*****************************************************************/


class Binaerknoten {

 // Attribute

 Object wert;   // Eintrag des Knotens: kann jedes beliebige Objekt sein

 String wertDarstellung;  // Stringdarstellung des Eintrags,
                          // wird bei einer Bildschirmanzeige des Knotens ausgegeben

 Binaerknoten linkerSohn,   // Verweis auf den linken Sohn
              rechterSohn;  // Verweis auf den rechten Sohn

 // Konstruktor: besetzt die vier Attribute mit den uebergebenen Werten vor

 Binaerknoten(Object wert, String wertDarstellung, Binaerknoten linkerSohn, Binaerknoten rechterSohn) {
  this.wert = wert;
  this.wertDarstellung = wertDarstellung;
  this.linkerSohn = linkerSohn;
  this.rechterSohn = rechterSohn;
 }

}


/***********************************************************************

   Die Klasse 'BinaerbaumTest' definiert Methoden zur Ein- und Ausgabe
   von Baeumen und enthaelt ein Hauptprogramm, in dem diese Methoden
   aufgerufen werden.
   
************************************************************************/


public class BinaerbaumTest {


 /* Methode zum Einlesen eines Binaerbaums.
    Der Baum wird Ebene fuer Ebene eingelesen, d.h. zunaechst die Wurzel,
    dann deren beiden Soehne, dann die Soehne dieser Knoten usw.
    Rueckgabewert ist ein Verweis auf das Wurzelobjekt. */

 static Binaerknoten baumEinlesen() throws IOException {

  BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

  Binaerknoten wurzel; // Wurzel des neuen Baums
  String eingabetext;  // Text zum Einsetzen in einen neuen Knoten

  // Einlesen des Wurzelknotens
  System.out.print("Bitte Wurzeleintrag (oder RETURN, wenn der Baum leer ist) eingeben: ");
  eingabetext = in.readLine();
  
  if (eingabetext.length()==0) {
   // Rueckkehr, wenn Wurzelknoten leer
   System.out.println("Baum ist leer");
   return null;
  }

  // Erzeugung des neuen Wurzelknoten
  wurzel = new Binaerknoten(eingabetext,eingabetext,null,null);

  // Erzeugung einer Liste: Enthaelt die Knoten, deren Soehne noch eingegeben werden muessen.
  ArrayList nochOffeneSoehne = new ArrayList();
  nochOffeneSoehne.add(wurzel);

  // Schleife, die so lange laeuft, wie noch Soehne eingegeben werden muessen
  while (!nochOffeneSoehne.isEmpty()) {

   // Auslesen des ersten Knotens mit noch offenen Sohneintraegen aus der Liste
   Binaerknoten aktKnoten = (Binaerknoten) nochOffeneSoehne.remove(0);

   // Eingabe des Eintrags des linken Sohns fuer diesen Knoten
   System.out.println();
   System.out.print("Bitte linken Sohn von " + aktKnoten.wertDarstellung + " oder RETURN (wenn nicht vorhanden) eingeben: ");
   eingabetext = in.readLine();
   if (eingabetext.length()!=0) {
    // Verweis des Knotens auf seinen neuen linken Sohn setzen
    aktKnoten.linkerSohn = new Binaerknoten(eingabetext,eingabetext,null,null);
    // Einfuegen des neuen linken Sohns in die Liste 
    nochOffeneSoehne.add(aktKnoten.linkerSohn);
   }

   // Analog: Eingabe des rechten Sohns
   System.out.println();
   System.out.print("Bitte rechten Sohn von " + aktKnoten.wertDarstellung + " oder RETURN (wenn nicht vorhanden) eingeben: ");
   eingabetext = in.readLine();
   if (eingabetext.length()!=0) {
    aktKnoten.rechterSohn = new Binaerknoten(eingabetext,eingabetext,null,null);
    nochOffeneSoehne.add(aktKnoten.rechterSohn);

   }

  }

  return wurzel;

 }


 /* Methode zur Ausgabe der Eintraege eines Binaerbaums in Preorder */

 static void ausgabePreorder(Binaerknoten wurzel) {

  if (wurzel!=null) {

   // Ausgabe der Wurzel
   System.out.print(wurzel.wertDarstellung+" ");

   // Ausgabe des linken Unterbaums in Preorder
   ausgabePreorder(wurzel.linkerSohn);

   // Ausgabe des rechten Unterbaums in Preorder
   ausgabePreorder(wurzel.rechterSohn);

  }

 }


 /* Methode zur Ausgabe der Eintraege eines Binaerbaums in Inorder */

 static void ausgabeInorder(Binaerknoten wurzel) {

  if (wurzel!=null) {

   // Ausgabe des linken Unterbaums in Inorder
   ausgabeInorder(wurzel.linkerSohn);

   // Ausgabe der Wurzel
   System.out.print(wurzel.wertDarstellung+" ");

   // Ausgabe des rechten Unterbaums in Inorder
   ausgabeInorder(wurzel.rechterSohn);

  }

 }


 /* Methode zur Ausgabe der Eintraege eines Binaerbaums in Postorder */

 static void ausgabePostorder(Binaerknoten wurzel) {

  if (wurzel!=null) {

   // Ausgabe des linken Unterbaums in Postorder
   ausgabePostorder(wurzel.linkerSohn);

   // Ausgabe des rechten Unterbaums in Postorder
   ausgabePostorder(wurzel.rechterSohn);

   // Ausgabe der Wurzel
   System.out.print(wurzel.wertDarstellung+" ");

  }

 }


 /* Methode zur Ausgabe der Baumstruktur: Der Baum wird auf einer zeichenorientierten
    Oberflaeche ausgegeben. Er wird dabei um 90 Grad gegen den Uhrzeigersinn gedreht,
    und die Tiefe der Knoten wird durch Einrueckungen angedeutet. */

 static void ausgabeStruktur(Binaerknoten wurzel, int einrueck) {
  // Parameter einrueck gibt an, um wie weit die Darstellung
  // des Wurzelknotens nach rechts eingerueckt werden soll

  if (wurzel!=null) {

   // Ausgabe des rechten Unterbaums mit einer um 4 groesseren Einrueckung
   ausgabeStruktur(wurzel.rechterSohn,einrueck+4);

   // Ausgabe des Wurzelknoten, eingerueckt um 'einrueck' Positionen
   for (int i=0;i<einrueck;i++)
    System.out.print(" ");
   System.out.println(wurzel.wertDarstellung+" ");

   // Ausgabe des linken Unterbaums mit einer um 4 groesseren Einrueckung
   ausgabeStruktur(wurzel.linkerSohn,einrueck+4);

  }

 }


 /* Methode zur graphischen Darstellung eines Binaerbaums */

 static void zeichne(Binaerknoten wurzel, Graphics g, int spalteLinks, int spalteRechts, int zeileOben, int zeileUnten) {
  // Die vier int-Parameter definieren ein Rechteck innerhalb des Grafik-Kontexts g,
  // innerhalb dessen gezeichnet werden soll
 
  if (wurzel!=null) {

   int spalteWurzel = (spalteLinks+spalteRechts)/2; // Spaltenposition der Wurzel

   // Wert des Wurzelknotens darstellen (obere Zeile, mittlere Spalte)
   g.setFont(new Font("Times Roman",Font.BOLD,22));
   g.drawString(wurzel.wertDarstellung,spalteWurzel,zeileOben);

   // linken Unterbaum in einem kleineren Rechteck links darunter zeichnen
   zeichne(wurzel.linkerSohn,g,spalteLinks,spalteWurzel,zeileOben+80,zeileUnten);

   // rechten Unterbaum in einem kleineren Rechteck rechts darunter zeichnen
   zeichne(wurzel.rechterSohn,g,spalteWurzel,spalteRechts,zeileOben+80,zeileUnten);

   // Kanten zeichnen
   if (wurzel.linkerSohn!=null)
    g.drawLine(spalteWurzel-10,zeileOben+10,(spalteLinks+spalteWurzel)/2+10,zeileOben+60);
   if (wurzel.rechterSohn!=null)
    g.drawLine(spalteWurzel+10,zeileOben+10,(spalteRechts+spalteWurzel)/2-10,zeileOben+60);
   
  }

 }


 /* JFrame zur Aufnahme einer Baumgrafik */

 static class BaumgrafikFrame extends JFrame {

  Binaerknoten wurzel;  // Wurzel des zu zeichnenden Baums
  
  // Panel, in dem gezeichnet wird
  
  class BaumgrafikPanel extends JPanel {

     // paint: zeichnet mit Hilfe der Methode zeichne() die Baumgrafik

     public void paint(Graphics g) {
      zeichne(wurzel,g,10,964,50,708);
     }

  }

  // Konstruktor fuer umschliessenden Rahmen
  
  public BaumgrafikFrame(Binaerknoten wurzel) {

   super();
   this.wurzel = wurzel;
   setForeground(Color.black);
   setBackground(Color.white);
   setFont(new Font("Dialog",Font.BOLD,12));
   getContentPane().add(new BaumgrafikPanel());
   setSize(974,718);
   setLocation(50,50);
   setVisible(true);

  }

 }

 /* Hilfsmethode zur Verzoegerung der weiteren Ausfuehrung */

 static void weiter() {
  try {
   BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
   System.out.println();
   System.out.println();
   System.out.print("--- Weiter: Bitte Return-Taste druecken");
   in.readLine(); 
  }
  catch (IOException e) { }

 }


 /* Hauptprogramm */

 public static void main(String args[]) throws IOException {

  Binaerknoten wurzel;

  System.out.println();
  System.out.println("Eingabe des Baums: ");
  System.out.println();

  wurzel = baumEinlesen();

  weiter();

  System.out.println();
  System.out.println();
  System.out.print("Baum in Preorder: ");

  ausgabePreorder(wurzel);

  System.out.println();
  weiter();

  System.out.println();
  System.out.println();
  System.out.print("Baum in Inorder: ");

  ausgabeInorder(wurzel);

  System.out.println();
  weiter();

  System.out.println();
  System.out.println();
  System.out.print("Baum in Postorder: ");

  ausgabePostorder(wurzel);

  System.out.println();
  weiter();

  System.out.println();
  System.out.println();
  System.out.println("Struktur des Baums: ");
  System.out.println();

  ausgabeStruktur(wurzel,0);

  weiter();

  new BaumgrafikFrame(wurzel);

  System.out.println();
  System.out.println("Grafik wird in gesondertem Fenster angezeigt");
  System.out.println();
  System.out.println("--- Programm mit Control-C beenden");

 } 

}