#include <iostream.h>
#include <fstream.h>
#include <iomanip.h>
#include <string.h>

struct BaumKnoten
   {
   int Schluessel;
   BaumKnoten* links;
   BaumKnoten* rechts;
   };

typedef BaumKnoten* BaumPtr;

class Suchbaum
{
public:
   Suchbaum();     // Kosntruktur erschafft leeren Suchbaum
   int suche(int Wert) const;
   void einfuege(int Wert);  // fuegt Wert in Baum ein
   int loesche(int Wert);    // loescht Wert aus Baum

   void GebausOrder(int Modus) const;   // gibt Baum aus in Nachordnung
   void OrderImplement(BaumPtr Wurzel, int Modus) const;  // Rekursion von GebausPostOrder
   int isEmpty() const;           // liefert 1 falls Baum leer
   int Gross() const;             // gibt Anzahl der Element aus Baum

 //  BaumPtr Wurzel;   // Pointer auf Wurzel des Baums
};
BaumPtr Wurzel;   // Pointer auf Wurzel des Baums
int Groesse;      // Anzahl Knoten in Baum


//Suchbaum::Suchbaum():Wurzel(NULL),Groesse(0){}

int Suchbaum::suche(int Wert) const
{
   BaumPtr p = Wurzel;
   while (p != NULL) // iterativ nach unten gehen
      {
      if (p->Schluessel == Wert)  // gefunden!
         {
         return 1;
         }
      else if (Wert < p->Schluessel) p = p->links;
      else p = p->rechts;
      }
   return 0;  // nicht gefunden
   }

void Suchbaum::einfuege(int Wert)
   {
   cout << "Einfuege "<< Wert<<"\n";
   BaumPtr p = new BaumKnoten;   // neuen Knoten erschaffen
   p->Schluessel = Wert;
   p->links = NULL;
   p->rechts = NULL;
   if (Wurzel == NULL)  // Baum ist leer
      {
      Wurzel = p;
      cout <<"Baum ist leer!\n";
      //Groesse++;
      return;
      }
   
   BaumPtr r = Wurzel;
   int fertig = 0;
   while (!fertig)
      {
		if (Wert < r->Schluessel)
         if (r->links == NULL)  // falls linker Sohn noch nicht existiert...
            {                  // ... dann koennen wir das Element da anfuegen
            r->links = p; 
            fertig = 1;
            }
         else r = r->links;       // sonst muessen wir weiter links runter

      else // Wert >= p->Schluessel 
         if (r->rechts == NULL)  // analog mit der rechten Seite.
            {
            r->rechts = p;
            fertig = 1;
            }
         else r = r->rechts;
      }
   Groesse++;
   cout << "Hab " << Wert << " eingefuegt. ";
   cout << "Baum hat nun " << Groesse << " Eintraege.\n";
   }

int Suchbaum::loesche(int Wert) // falls Element Wert existiert,
{                               // so soll es geloescht werden.
   BaumPtr p = Wurzel;          // Beginne bei der Wurzel
   BaumPtr eltern = NULL;
   int gefunden = 0;
   while (p != NULL && !gefunden)  // solange Element nicht gefunden und wir noch
      {                             // nicht unten angekommen sind
      if (p->Schluessel == Wert) gefunden = 1;
      else if (Wert < p->Schluessel) // links runter
         {
         eltern = p;
         p = p->links;
         }
     else                           // rechts runter
         {
         eltern = p;
         p = p->rechts;
         }
      }

   if (!gefunden) return 0; // wir sind unten angekommen ohne Erfolg

   if (p->rechts == NULL && p->links == NULL) // Wir sind in Blatt
      {
      if (p == Wurzel) Wurzel = NULL;  // Wir sind noch in Wurzel des Baumes,
                                       // es sind also keine Eltern zu modifizieren.
      else if (eltern->rechts == p) eltern->rechts = NULL; // Eltern haben
                                                           // rechten Sohn verloren
      else eltern->links = NULL;
      delete p;
      }
   else if (p->links == NULL)  // kein linker Sohn
      {
      if (p == Wurzel) Wurzel = p->rechts;
      else if (eltern->rechts == p) eltern->rechts = p->rechts;
                                 // Eltern werden mit ihren Enkeln verbunden
      else eltern->links = p->rechts;
      delete p;
      }
   else if (p->rechts == NULL)  // kein rechter Sohn
      {
      if (p == Wurzel) Wurzel = p->links;
      if (eltern->rechts == p) eltern->rechts = p->links;
      else eltern->links = p->links;
      delete p;
      }
   else  // Knoten hat zwei Knoten
      {
      BaumPtr runter = p->links;  // Suche nach rechtstem Knoten in linkem Teilbaum
      BaumPtr runtereltern = p;   
      while (runter->rechts != NULL)
         {
         runtereltern = runter;
         runter = runter->rechts;
         }
      // runter enthaelt nun groesstes Element links von p
      if (runtereltern == p) runtereltern->links = runter->links;
      else runtereltern->rechts = runter->links;
      p->Schluessel = runter->Schluessel;
      delete runter;
      }
   Groesse--;
   cout << "Hab " << Wert << " geloescht. ";
   cout << "Baum hat nun " << Groesse << " Eintraege.\n";
   return 1;
   }

void Suchbaum::GebausOrder (int Modus) const // Modus= 0 => Preorder
   {                          // 1 => Inorder, 2 => Postorder
   BaumPtr p = Wurzel;
   if (Modus==0) cout << "Preorder: ";
   if (Modus==1) cout << "Inorder: ";
   if (Modus==2) cout << "Postorder: ";
   OrderImplement (p, Modus);
   cout << "\n";
	}
void Suchbaum::OrderImplement (BaumPtr p, int Modus) const
   {
   if (p!=NULL)
      {
      if (Modus==0) cout <<" <"<< p->Schluessel << "> ";
      OrderImplement (p->links, Modus);
      if (Modus==1) cout <<" <"<< p->Schluessel << "> ";
      OrderImplement (p->rechts, Modus);
      if (Modus==2) cout <<" <"<< p->Schluessel << "> ";
      }
   }




int Suchbaum::isEmpty() const
   {
   return Wurzel == NULL;
   }

int Suchbaum::Gross() const
   {
   return Groesse;
   }



void main (void)
{
   cout << "a";
   Suchbaum *Baeumchen;

   Baeumchen->einfuege(8);
   Baeumchen->einfuege(2);
   Baeumchen->einfuege(1);
   Baeumchen->einfuege(15);
   Baeumchen->einfuege(20);
   Baeumchen->einfuege(17);
   Baeumchen->einfuege(3);
   Baeumchen->einfuege(10);
   Baeumchen->GebausOrder(0); // Vorordung
   Baeumchen->GebausOrder(1); // Zwischenordung
   Baeumchen->GebausOrder(2); // Nachordung
   Baeumchen->loesche (2);

   Baeumchen->GebausOrder(0); // Vorordung
   Baeumchen->GebausOrder(1); // Zwischenordung
   Baeumchen->GebausOrder(2); // Nachordung
   cout << "Suche 3 : " << Baeumchen->suche (3)<<"\n";
   cout << "Suche 317 : " << Baeumchen->suche (317)<<"\n";

cout << "\n";
}