//Binaerer Suchbaum
import java.*;
import java.lang.*;
// Knoten des Suchbaums
class BKnoten
{
int Wert;
BKnoten links;
BKnoten rechts;
BKnoten()
{
int Wert;
links = null;
rechts = null;
}
BKnoten(int Wert)
{
this.Wert = Wert;
links = null;
rechts = null;
}
}
//
// der Baum
//
class bSBaum
{
public static String newline = System.getProperty("line.separator");
BKnoten wurzel;
// ein bsBaum mit Wurzel null;
bSBaum (){wurzel = null;}
//
// Einen Knoten anhaengen
//
// die Seite an der eingefuegt wird, wird je nach groeße der Zahl bestimmt
void put (int Wert)
{
BKnoten aktueller = wurzel;
BKnoten frueherer = aktueller;
if (wurzel == null)
{wurzel = new BKnoten(Wert);}
else
{
boolean eingefuegt = false;
while (eingefuegt == false)
{
frueherer = aktueller;
if (Wert < aktueller.Wert)
{
if (aktueller.links == null)
{
aktueller.links = new BKnoten(Wert);
eingefuegt = true;
}
aktueller = aktueller.links;
}
else
{
if (aktueller.rechts == null)
{
aktueller.rechts = new BKnoten(Wert);
eingefuegt = true;
}
aktueller = aktueller.rechts;
}
}
}
}
//
// Den Knoten mit dem Wert Wert loeschen
//
boolean loeschen (int Wert) {
boolean geloescht = true;
BKnoten aktueller = wurzel;
BKnoten frueherer = aktueller;
while (aktueller != null) {
if (Wert > aktueller.Wert) {
frueherer = aktueller;
aktueller = aktueller.rechts;
}
else if (Wert < aktueller.Wert) {
frueherer = aktueller;
aktueller = aktueller.links;
}
else if (Wert == aktueller.Wert) {
geloescht = false;
break;
}
}
if (pruefe(aktueller) == 0)
{
if (aktueller.Wert > frueherer.Wert)
{frueherer.rechts = null;}
else
{frueherer.links = null;}
}
else if (pruefe(aktueller) == 1)
{
if (aktueller.Wert > frueherer.Wert)
{
if (aktueller.links != null)
{frueherer.rechts = aktueller.links;}
else {frueherer.rechts = aktueller.rechts;}
}
else
{
if (aktueller.links != null)
{frueherer.links = aktueller.links;}
else
{frueherer.links = aktueller.rechts;}
}
}
else if (pruefe(aktueller) == 2)
{
BKnoten temp = inord(aktueller);
if (aktueller == wurzel)
{wurzel.Wert = temp.Wert;}
else
{
if (aktueller.Wert > frueherer.Wert)
{frueherer.rechts.Wert = temp.Wert;}
else{frueherer.links.Wert = temp.Wert;}
}
}
return geloescht;
}
//
BKnoten inord (BKnoten a)
{
int t = 0;
BKnoten ret, frueherer = new BKnoten();
frueherer = a;
a = a.rechts;
while (a.links != null)
{
frueherer = a;
a = a.links;
t = 1;
}
ret = a;
if (t == 0)
{frueherer.rechts = null;}
else
{frueherer.links = null;}
a = null;
return ret;
}
//
// Pruefe, ob der Knoten a existiert
//
int pruefe(BKnoten a)
{
int ret;
if ((a.links != null) && (a.rechts != null))
{ret = 2;}
else if ((a.links == null) && (a.rechts == null))
{ret = 0;}
else
{ret = 1;}
return ret;
}
// !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
// Gibt den Knoten a am Bildschirm aus (preorder)
// !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
void printKnoten(BKnoten oot)
{
if (oot.links != null)
{printKnoten(oot.links);}
// Wert + Leerzeile
System.out.print(oot.Wert + " ");
if (oot.rechts != null)
{printKnoten(oot.rechts);}
}
// Inorder
void printKnotenInorder(BKnoten oot)
{
System.out.print(oot.Wert + " ");
if (oot.links != null)
{printKnotenInorder(oot.links);}
// Wert + Leerzeile
if (oot.rechts != null)
{printKnotenInorder(oot.rechts);}
}
void printKnotenPostorder(BKnoten oot)
{
if (oot.links != null)
{printKnotenPostorder(oot.links);}
// Wert + Leerzeile
if (oot.rechts != null)
{printKnotenPostorder(oot.rechts);}
System.out.print(oot.Wert + " ");
}
//
// Gibt den Knoten a aus, gefolgt von einem Zeilenwechsel
//
void printKnotenln (BKnoten oot)
{
printKnoten(oot);
System.out.print(newline);
}
void mehrfachLoeschen (int ... oots)
{
for (int i = 0; i < oots.length; i++)
{loeschen (oots[i]);}
}
void mehrfachPut (int ... oots)
{
for (int i = 0; i < oots.length; i++)
{put (oots[i]);}
}
public static void main(String[] args)
{
bSBaum a = new bSBaum();
/*a.put(8);
a.put(7);
a.put(5);
a.put(4);
a.put(6);
a.put(3);
a.put(2);
a.put(1);
a.put(9);*/
a.mehrfachPut (8, 7, 5, 4, 6, 3, 2, 1, 9);
//a.printKnoten(a.wurzel);
System.out.println ("Preorder:");
a.printKnoten(a.wurzel);
System.out.println();
System.out.println ("Inorder:");
a.printKnotenInorder(a.wurzel);
System.out.println();
System.out.println ("Postorder:");
a.printKnotenPostorder(a.wurzel);
System.out.println();
/*a.loeschen(8);
a.loeschen(5);*/
a.mehrfachLoeschen(8, 5);
//System.out.println("=================================");
//a.printKnoten(a.wurzel);
System.out.println ("Preorder:");
a.printKnoten(a.wurzel);
System.out.println();
System.out.println ("Inorder:");
a.printKnotenInorder(a.wurzel);
System.out.println();
System.out.println ("Postorder:");
a.printKnotenPostorder(a.wurzel);
System.out.println();
//System.out.println ("Inorder:");
//inord(a.wurzel);
}
}
