/****************************************************************/
/* Prof. Dr. Carsten Vogt                                       */
/* FH Koeln, Fak. 07 / Nachrichtentechnik                       */
/* http://www.nt.fh-koeln.de/vogt                               */
/*                                                              */
/* Das Programm definiert Methoden zum Umgang mit Suchbaeumen   */
/* und ein Hauptprogramm zum Test dieser Methoden.              */
/****************************************************************/

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


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

   Die Klasse 'Binaerknoten' definiert Knoten in Binaerbaeumen
   (siehe auch BinaerknotenTest.java).

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


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 übergebenen 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 'Suchbaumknoten' definiert Knoten in Suchbaeumen.
   Sie ist eine Erweiterung der Klasse 'Binaerknoten' und ergaenzt
   den Knoteneintrag 'wert' durch ein Comparable-Attribut 'schluessel',
   über den dann Knoteneintraege per 'compareTo()' verglichen werden
   koennen.
   Zudem hat die Klasse ein Attribut, das auf den Vaterknoten verweist,
   und eine Hilfsmethode zum konsistenten Setzen eines Sohnattributs.

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


class Suchbaumknoten extends Binaerknoten {

 // Attribute

 Comparable schluessel;  // Schlüsseleintrag des Knotens, anhand dessen
                         // Knoten verglichen werden koennen

 Suchbaumknoten vater;  // Verweis auf den Vaterknoten:
                        // ist zwar von der Suchbaumdefinition her nicht erforderlich,
                        // erleichtert aber die Programmierung der Methode zum Ausfügen von Knoten.

 // Konstruktor: besetzt die sechs Attribute mit den übergebenen Werten vor

 Suchbaumknoten(Object wert, Comparable schluessel, String wertDarstellung,
                 Suchbaumknoten linkerSohn, Suchbaumknoten rechterSohn, Suchbaumknoten vater) {
  super(wert,wertDarstellung,linkerSohn,rechterSohn);
  this.schluessel = (Comparable)schluessel;
  this.vater = vater;
 }

 // Hilfsmethode zum Setzen des Attributs 'linkerSohn' oder 'rechterSohn'.
 // Sie setzt insbesondere im Sohn das 'vater'-Attribut korrekt.

 void setSohn(Suchbaumknoten neuerSohn, char welcherSohn) {
  if (welcherSohn=='l')
    this.linkerSohn = neuerSohn;
   else
    this.rechterSohn = neuerSohn;
  if (neuerSohn!=null)
   neuerSohn.vater=this;
 }

}


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

   Die Klasse 'SuchbaumMethoden' definiert Methoden zur Arbeit mit Suchbaeumen:
   einfuegen(): Einfügen eines neuen Knotens in einen Suchbaum
   entfernen(): Entfernen eines Knotens aus einem Suchbaum
   suchen():    Suchen nach einem Knoten in einem Suchbaum
   zeichnen():  grafische Ausgabe eines Suchbaums

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


class SuchbaumMethoden {


 /* Methode zum Einfügen eines neuen Knotens 'neuKnoten'
    in einen Suchbaum mit dem Wurzelknoten 'wurzel'.
    Sie arbeitet nur auf Baeumen, die schon mindestens einen Knoten
    besitzen.
    Die Methode gibt -1 zurück, wenn das Einfügen nicht erfolgreich war
    (insbesondere, wenn der Baum leer ist oder ein Knoten mit dem
    entsprechenden Text schon im Baum enthalten ist), und 0 sonst.
 */

 static int einfuegen(Suchbaumknoten wurzel, Suchbaumknoten neuKnoten) {

  if (wurzel==null || wurzel.wertDarstellung.equals(neuKnoten.wertDarstellung))
   // Einfügen fehlgeschlagen, da keine Wurzel vorhanden oder die Wurzel
   // den einzufügenden Wert bereits enthaelt
   return -1;

  if (wurzel.schluessel.compareTo(neuKnoten.schluessel)>0)
   // Einfügen in den linken Unterbaum, da Wurzelwert groesser ist als der neue Wert
   if (wurzel.linkerSohn==null) {
     // wenn Wurzel keinen linken Sohn hat: neuKnoten ist der neue linke Sohn
     wurzel.setSohn(neuKnoten,'l');
     return 0; }
    else
     // sonst Einfügen des neuen Knotens in den linken Unterbaum der wurzel
     return einfuegen((Suchbaumknoten)wurzel.linkerSohn,neuKnoten);

  // Einfügen in den rechten Unterbaum,
  // da aufgrund der vorherigen Tests der neue Wert groesser sein muss als der Wurzelwert
  if (wurzel.rechterSohn==null) {
     wurzel.setSohn(neuKnoten,'r');
    return 0; }
   else
    return einfuegen((Suchbaumknoten)wurzel.rechterSohn,neuKnoten);

 }

 /* Methode zum Suchen des Knotens mit dem minimalen Schlüsseleintrag,
    die als Hilfsmethode beim Ausfügen eines Knotens gebraucht wird.
    Rückgabewert: Verweis auf den Knoten mit dem minimalen Schlüssel. */

 static Suchbaumknoten sucheMinimum(Suchbaumknoten wurzel) {

  // Der Knoten mit dem minimalen Eintrag
  // ist der am weitesten links stehende Knoten im Baum
  Suchbaumknoten minKnoten = wurzel;
  while (minKnoten.linkerSohn!=null)
   minKnoten = (Suchbaumknoten) minKnoten.linkerSohn;
  return minKnoten;

 }

 /* Methode zum Entfernen eines Knotens mit dem Schlüssel 'auszufuegenderSchluessel'
    aus einem Suchbaum mit dem Wurzelknoten 'wurzel'. Enthaelt der Baum keinen
    passenden Knoten, so geschieht nichts.
    Rückgabewert: Verweis auf die Wurzel des Baums nach dem Ausfügen. */

 static Suchbaumknoten entfernen(Suchbaumknoten wurzel, Comparable auszufuegenderSchluessel) {

  Suchbaumknoten auszufuegen; // auszufügender Knoten

  // Suche nach dem auszufügenden Knoten

  auszufuegen = suchen(wurzel,auszufuegenderSchluessel);

  // Fall 1: kein entsprechender Knoten im Baum vorhanden

  if (auszufuegen==null)
   return wurzel;

  // Fall 2: auszufügender Knoten ist die Wurzel

  if (auszufuegen==wurzel) {
   if (wurzel.linkerSohn==null)
    // Wurzel hat nur einen rechten Unterbaum
    //  -> Wurzel durch den Wurzelknoten dieses Unterbaums ersetzen
    wurzel=(Suchbaumknoten)wurzel.rechterSohn;
   else if (wurzel.rechterSohn==null)
    // Wurzel hat nur einen linken Unterbaum
    //  -> Wurzel durch den Wurzelknoten dieses Unterbaums ersetzen
    wurzel=(Suchbaumknoten)wurzel.linkerSohn;
   else { // Wurzel hat linken und rechten Unterbaum
    // minimalen Knoten im rechten Unterbaum der Wurzel suchen
    Suchbaumknoten minKnoten = sucheMinimum((Suchbaumknoten)wurzel.rechterSohn);
    // minimalen Knoten von seiner bisherigen Stelle entfernen
    Suchbaumknoten unterbaumRechtsNeu = entfernen((Suchbaumknoten)wurzel.rechterSohn,minKnoten.schluessel);
    wurzel.setSohn(unterbaumRechtsNeu,'r');
    // minimalen Knoten anstelle der Wurzel einsetzen
    minKnoten.setSohn((Suchbaumknoten)wurzel.linkerSohn,'l');
    minKnoten.setSohn((Suchbaumknoten)wurzel.rechterSohn,'r');
    wurzel = minKnoten;
   }
   if (wurzel!=null)
    // Baumwurzel hat keinen Vater
    wurzel.vater=null;
   return wurzel;
  }

  // Fall 3: auszufügender Knoten ist nicht die Wurzel

  Suchbaumknoten vater = auszufuegen.vater; // Vater des auszufügenden Knotens

  if (auszufuegen==vater.linkerSohn) {
    // 'auszufuegen' aus dem Unterbaum ausfügen, dessen Wurzel er ist,
    Suchbaumknoten linkerUnterbaumNeu = entfernen(auszufuegen,auszufuegenderSchluessel);
    // und die neue Wurzel dieses Unterbaums als linken Sohn des Vaters einsetzen
    vater.setSohn(linkerUnterbaumNeu,'l');
   }
   else {
    // 'auszufuegen' aus dem Unterbaum ausfügen, dessen Wurzel er ist,
    Suchbaumknoten rechterUnterbaumNeu = entfernen(auszufuegen,auszufuegenderSchluessel);
    // und die neue Wurzel dieses Unterbaums als rechten Sohn des Vaters einsetzen
    vater.setSohn(rechterUnterbaumNeu,'r');
   }

  return wurzel;

 }


 /* Methode zur Suche eines Knotens mit dem Schlüssel 'gesuchterSchluessel'
    in einem Suchbaum mit dem Wurzelknoten 'wurzel'.
    Rückgabewert: Verweis auf das gefundene Knotenobjekt
     oder null, wenn kein entsprechender Knoten vorhanden. */

 static Suchbaumknoten suchen(Suchbaumknoten wurzel, Comparable gesuchterSchluessel) {

  if (wurzel==null)
   // gesuchter Wert ist im Baum nicht vorhanden
   return null;

  if (wurzel.schluessel.equals(gesuchterSchluessel))
   // Wurzelknoten enthaelt gesuchten Schlüssel
   return wurzel;

  if (wurzel.schluessel.compareTo(gesuchterSchluessel)>0)
   // Gesuchter Schlüssel ist, wenn überhaupt, im linken Unterbaum:
   // Daher wird dort weitergesucht und das von dort kommende Suchergebnis
   // per return nach oben weitergegeben.
   return suchen((Suchbaumknoten)wurzel.linkerSohn,gesuchterSchluessel);

  // Da alle anderen Faelle ausgeschlossen sind, kann der gesuchte Schlüssel
  // hoechstens im rechten Unterbaum sein
  return suchen((Suchbaumknoten)wurzel.rechterSohn,gesuchterSchluessel);

 }


 /* Methode zur graphischen Darstellung eines Binaerbaums */

 static void zeichnen(Suchbaumknoten 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 Knotens darstellen (obere Zeile, mittlere Spalte)
   g.setFont(new StandardFont());
   g.drawString(wurzel.wertDarstellung,spalteWurzel,zeileOben);

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

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

   // Kanten von der Wurzel zu ihren beiden Soehnen 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);

  }

 }

}


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

   Die folgenden Klassen definieren die grafische Oberflaeche des Programms.

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

/* standardmaessig verwendeter Font */

class StandardFont extends Font {
 StandardFont() {
  super("Arial",Font.BOLD,20);
 }
}

/* Label zur Anzeige von Textkonstanten */

class StandardLabel extends JLabel {
 StandardLabel(String str) {
  super(str);
  setFont(new StandardFont());
  setForeground(Color.black);
 }
}

/* Textfeld zur Eingabe von Strings */

class StandardTextfeld extends JTextField {
 StandardTextfeld() {
  super();
  setFont(new StandardFont());
  setForeground(Color.black);
 }
}

/* Button */

class StandardButton extends JButton {
 StandardButton(String text) {
  super(text);
  setFont(new StandardFont());
  setForeground(Color.black);
 }
}

/* Hauptfenster, das beim Programmstart erscheint */

class Hauptfenster extends JFrame {

 Suchbaumknoten hauptWurzel;  // Wurzelknoten des zugrundeliegenden Suchbaums

 BaumgrafikFrame baumgrafik;  // Rahmen für die zugehoerige grafische Darstellung

 // Textfelder zur Eingabe von Strings,
 // mit denen dann Aktionen auf dem Suchbaum ausgeführt werden

 JTextField einfuegeTextFeld = new StandardTextfeld(),  // zum Einfügen eines neuen Knotens
            entferneTextFeld = new StandardTextfeld(),  // zum Entfernen eines Knotens
            sucheTextFeld    = new StandardTextfeld();  // zur Suche nach einem Knoten

 // Button zur Beendigung des Programms

 JButton endeButton = new StandardButton("Ende");

 // Konstruktor

 Hauptfenster(Suchbaumknoten hauptWurzel) {

  super();

  // Setzen des Wurzelknotens
  this.hauptWurzel = hauptWurzel;

  // Definition von Ort und Layout der Darstellung
  setLocation(20,50);
  getContentPane().setLayout(new GridLayout(7,1));


  // Hinzufügen der Eingabefelder, des Ende-Buttons und zugehoeriger Beschriftungen
  getContentPane().add(new StandardLabel("Einfügen:"));
  getContentPane().add(einfuegeTextFeld);
  getContentPane().add(new StandardLabel("Entfernen:"));
  getContentPane().add(entferneTextFeld);
  getContentPane().add(new StandardLabel("Suchen:"));
  getContentPane().add(sucheTextFeld);
  getContentPane().add(endeButton);


  // Anbinden von Listenern an die Textfelder und den Button
  einfuegeTextFeld.addActionListener(new EinfuegeListener());
  entferneTextFeld.addActionListener(new EntferneListener());
  sucheTextFeld.addActionListener(new SucheListener());
  endeButton.addActionListener(new EndeListener());

  // Erzeugung eines zugehoerigen Rahmens zur grafischen Darstellung
  baumgrafik = new BaumgrafikFrame(hauptWurzel);

  pack();
  setVisible(true);

 }

 // Listener zum Start des Einfuegens eines neuen Knotens

 class EinfuegeListener implements ActionListener {

  public void actionPerformed(ActionEvent e) {

   Suchbaumknoten neuKnoten; // neuerKnoten
   String eingabetext;  // Text zum Einsetzen in den neuen Knoten

   // Erzeugung des neuen Knotens
   eingabetext = ((JTextField)e.getSource()).getText();
   neuKnoten = new Suchbaumknoten(eingabetext,eingabetext,eingabetext,null,null,null);

   // Einfuegen des neuen Knotens in den Suchbaum
   if (hauptWurzel==null)
     hauptWurzel = neuKnoten;
    else {
     int erg;
     erg = SuchbaumMethoden.einfuegen(hauptWurzel,neuKnoten);
     if (erg==-1)
      JOptionPane.showMessageDialog(null,"Einfuegen fehlgeschlagen","",JOptionPane.INFORMATION_MESSAGE);
    }

   // Neuanzeige der Baumgrafik
   baumgrafik.dispose();
   baumgrafik = new BaumgrafikFrame(hauptWurzel);

  }

 }


 // Listener zum Start des Entfernens eines Knotens

 class EntferneListener implements ActionListener {

  public void actionPerformed(ActionEvent e) {

   String auszufuegText;  // Schluesseltext des auszufuegenden Knotens

   // Entfernen des gewuenschten Knotens
   auszufuegText = ((JTextField)e.getSource()).getText();
   hauptWurzel = SuchbaumMethoden.entfernen(hauptWurzel,auszufuegText);

   // Neuanzeige der Baumgrafik
   baumgrafik.dispose();
   baumgrafik = new BaumgrafikFrame(hauptWurzel);

  }

 }

 // Listener zum Start der Suche nach einem Knoten

 class SucheListener implements ActionListener {

  public void actionPerformed(ActionEvent e) {

   String gesuchterText = ((JTextField)e.getSource()).getText();;
   if (SuchbaumMethoden.suchen(hauptWurzel,gesuchterText)!=null)
     JOptionPane.showMessageDialog(null,"Knoten gefunden","Suchergebnis",JOptionPane.INFORMATION_MESSAGE);
    else
     JOptionPane.showMessageDialog(null,"Knoten nicht gefunden","Suchergebnis",JOptionPane.INFORMATION_MESSAGE);
   }

 }

 class EndeListener implements ActionListener {

  public void actionPerformed(ActionEvent e) {

   // Ende des Programms
   System.exit(0);

  }

 }

}


/* Rahmen zur Aufnahme einer Baumgrafik */

class BaumgrafikFrame extends JFrame {

 Suchbaumknoten wurzel;  // Wurzel des zu zeichnenden Baums
 
 // Panel zum Zeichnen der Grafik
 
 class BaumgrafikPanel extends JPanel {

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

   public void paint(Graphics g) {
    SuchbaumMethoden.zeichnen(wurzel,g,10,864,50,708);
   }

 }

 // Konstruktor fuer umschliessenden Rahmen

 public BaumgrafikFrame(Suchbaumknoten wurzel) {

  super("Suchbaum:");
  this.wurzel = wurzel;
  setForeground(Color.black);
  setBackground(Color.white);
  setFont(new StandardFont());
  getContentPane().add(new BaumgrafikPanel());
  setSize(874,718);
  setLocation(150,50);
  setVisible(true);

 }

}


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

   Die Klasse 'SuchbaumTest' definiert ein Hauptprogramm, mit dem ein
   Suchbaum aufgebaut, veraendert und ausgegeben werden kann.

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


public class SuchbaumTest {

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

  // Erzeugung eines leeren Baums

  Suchbaumknoten hauptWurzel = null;

  // Erzeugung eines Bedienfensters
  // und einer grafischen Oberflaeche zur Darstellung des Baums

  new Hauptfenster(hauptWurzel);

 }

}