#include <iostream>

typedef int infotyp;


class suchBaum
{ private:
    infotyp info;
    int hoehe;
    suchBaum *LS, *RS;

    suchBaum* rotiere ();
    suchBaum* loesche_partner(infotyp &partnerinfo);

  public:
    suchBaum()// Konstruktor
    { 
    }
    suchBaum* suchen(infotyp was);
    suchBaum* einfuegen(infotyp was);
    suchBaum* loeschen(infotyp was);
    void preorder();
    void inorder();
    void postorder();
    void zeige();
};



suchBaum* suchBaum::suchen (infotyp was) // nach einem Element suchen
{ suchBaum *wo=this;  // Wurzel
  while (wo != NULL)
  { if (wo->info == was) break;
    if (wo->info < was ) wo = wo->RS;
       else wo = wo->LS;
  }
  return wo;
}

suchBaum* suchBaum::einfuegen(infotyp was)
{ if (this == NULL)
  { suchBaum *W = new suchBaum;
    W->info = was;
    W->RS  = NULL;
    W->LS = NULL;
    W->hoehe = 1;
    return W;
  }
  if (info == was) return this;
  if (info > was ) LS = LS->einfuegen (was);
     else RS = RS->einfuegen (was);
  return this;
}


suchBaum* suchBaum::loesche_partner(infotyp &partnerinfo)
{ if (RS == NULL)
  { partnerinfo = info;
    return LS;
  }
  RS = RS->loesche_partner(partnerinfo);
  return this;
}

suchBaum* suchBaum::loeschen(infotyp was)
{ // leerer Baum:
  if (this == NULL) return NULL;
  // Baum ist nicht leer; Loeschknoten noch nicht gefunden
  if (info != was )
  { if (info > was)
      LS = LS->loeschen (was);
    else
      RS =RS->loeschen (was);
    return this;
  }
  // Loeschknoten gefunden:
  int grad = 0;
  if (LS != NULL) grad++;
  if (RS != NULL) grad++;
  switch (grad)
  { case 0:   return NULL;
    case 1:   if (LS != NULL)
                  return LS;
              else
                  return RS;
    case 2:   infotyp i;
              LS = LS->loesche_partner(i);
              info = i;
              return this;
   }
  return this; 
}


void suchBaum::inorder()       // Baum ausgeben in Vorordnung
{ if (this==NULL) return;
  LS->inorder();
  cout << info<<"  Hoehe: " <<hoehe<< endl;
  RS->inorder();
}


void suchBaum::preorder()      // Baum ausgeben in Zwischenordnung
{ if (this==NULL) return;
  cout << info<<"  Hoehe: " <<hoehe<< endl;
  LS->preorder();
  RS->preorder();
}

void suchBaum::postorder()     // Baum ausgeben in Nachordnung
{ if (this==NULL) return;
  LS->postorder();
  LS->postorder();
  cout << info<<"  Hoehe: " <<hoehe<< endl;
}


char menu()                   // Benutzerinterface
{ char was;
  cout <<"\n\nAktion:\n";
  cout <<"\ne: Einfuegen";
  cout <<"\nl: Loeschen";
  cout <<"\ns: Suchen";
  cout <<"\na: Ausgeben";
  cout <<"\nv: Programm verlassen\n";
  cout <<"-> "; cin  >> was;
  return was;
}


int main(void)
{ int n;
  suchBaum *W=NULL;
  int weiter = 1;
  do
  { switch (menu())
    { case 'e' :  cout <<"\n Einfuegen: ";
                  cin >> n;
                  W = W->einfuegen(n);
                  break;
      case 'l' :  cout <<"\n Loeschen: ";
                  cin >> n;
                  W = W->loeschen(n);
                  break;
      case 's' :  cout <<"\n Suchen: ";
                  cin >> n;
                  if (W->suchen(n)== NULL)
                      cout<<"\n"<<n<<" ist nicht vorhanden\n";
                  else
                     cout<<"\n"<<n<<" ist vorhanden\n";
                  break;
      case 'a' :  if (W==NULL)
                    cout << "\n Der Baum ist leer \n";
                  else
                  { cout << "\n Der Baum in Inorder: \n";
                    W->inorder();
                    cout <<"\n\n.. und in Preorder:\n";
                    W->preorder();
                  }  
                  break;
      case 'v' :  cout << "Programm wird verlassen.\n";
                  return 0;
      default : weiter = 0;
    }
  } while  (weiter);
  cin >> n;
  return 0;
}