#include <stdio.h>
#include <string.h>
#include <stdlib.h>


struct binaer_knoten{
                      char ort[255];
                      unsigned int plz;
                      struct binaer_knoten *links;
                      struct binaer_knoten *rechts;
                    };


struct binaer_baum{
                   struct binear_knoten *root;
                   unsigned int counter;
                  };


struct binaer_baum *init()
{
 /*dynamisch Speicher allokieren*/
 struct binaer_baum *baum = malloc(sizeof *baum);
 if(baum == NULL) /*Speicher allokieren fehlgeschlagen ? */
   return NULL;
 else
  { /*Initialisieren*/
   baum->root = NULL;
   baum->counter=0;
   return baum;
  }
}


int einfuegen(struct binaer_baum *baum, unsigned int p, char o[])
{
 struct binaer_knoten *knoten, **neu;
 neu = &baum->root;
 knoten=  baum->root;

 for(;;)
  {
    if(knoten == NULL) /*Haben wir einen freien Platz gefunden?*/
     {
       knoten = *neu = malloc(sizeof *knoten);
       if(knoten!=NULL)
        {
         /*Daten rein damit*/
         knoten->plz = p;
         strcpy(knoten->ort, o);
         knoten->links=knoten->rechts=NULL;
         baum->counter++;
         return 1;
        }
       else
        return 0;
      }
    else if(p > knoten->plz) /*Ist die aktuelle Postleitzahl größer*/
      {
       /*Dann gehts recht weiter im Baum*/
       neu = &knoten->rechts;
       knoten = knoten->rechts;
      }
    else /*Der letzte Fall die aktuelle PLZ ist kleiner*/
      {
       /*dann eben nach links weiter im Baum*/
       neu = &knoten->links;
       knoten = knoten->links;
      }
   }
}


void binaere_suche_plz(const struct binaer_baum *baum, unsigned int p)
{
 const struct binaer_knoten *knoten;
 /*Zuerst an die Wurzel*/
 knoten = baum->root;

 for(;;)
  {
    if(knoten == NULL)
     {
      printf("Keine erfolgreiche Suche!\n");
      return;
     }
    if(p == knoten->plz) /*Gefunden*/
     {
      printf("Ort zu Postleitzahl %d : %s\n",p,knoten->ort);
      return;
     }
    else if(p > knoten->plz) /*Gesuchtes Element größer*/
      knoten=knoten->rechts; /*Rechts am Baum weiter*/
    else /*Gesuchtes Element kleiner*/
      knoten=knoten->links;  /*Links am Baum weiter*/
   }
}

int bin_delete(struct binaer_baum *baum, unsigned int p)
{ /*pointer_z ist das zu löschende Element*/
 struct binaer_knoten **pointer_q, *pointer_z, *pointer_y,*pointer_x;

 pointer_q = &baum->root;
 pointer_z =  baum->root;

 for(;;)
  {
    if(pointer_z == NULL)
      return 0;
    else if(p == pointer_z->plz) /*zu löschendes Element gefunden*/
      break;
    else if(p > pointer_z->plz) /*löschende Element ist größer*/
     {
       pointer_q = &pointer_z->rechts; /*rechts weitersuchen*/
       pointer_z = pointer_z->rechts;
     }
    else /*Löschende Element ist kleiner*/
     {
       pointer_q = &pointer_z->links; /*links weitersuchen*/
       pointer_z = pointer_z->links;
     }
   }/*Hierher kommen wir nur durch break*/

 /*Jetzt müssen wir das zu löschende Element untersuchen*/

 /*pointer_z hat rechts keinen Nachfolger, somit können wir
          es austauschen mit dem linken Nachfolger.......*/
  if(pointer_z->rechts == NULL)
    *pointer_q = pointer_z->links;
  else
    {
 /*pointer_z hat einen rechten Nachfolger aber keinen Linken.*/
      pointer_y = pointer_z->rechts;
      if(pointer_y->links == NULL)
      /*pointer_z->rechts hat keinen linken Nachfolger....*/
       {
         pointer_y->links = pointer_z->links;
         *pointer_q = pointer_y;
       }
      else
       { /* es gibt einen linken Nachfolger*/
         pointer_x = pointer_y->links;
         /*Jetzt suchen wir solange bis es keinen linken Nachfolger mehr gibt*/
         while(pointer_x->links != NULL)
          {
            pointer_y = pointer_x;
            pointer_x = pointer_y->links;
          }
         /*Jetzt haben wir alle Punkte zusammen und könne diese Verknüpfen*/
        pointer_y->links = pointer_x->rechts;
        pointer_x->links = pointer_z->links;
        pointer_x->rechts = pointer_z->rechts;
        *pointer_q = pointer_x;
       }
      }
    /*Zu guter letzt könne wir pointer_z freigeben*/
   baum->counter--;
   free(pointer_z);
   return 1;
}


int main()
{
 struct binaer_baum *re;
 char o[255];
 unsigned int p;
 int wahl,r;
 re = init();
 if(re == NULL)
  {
    fprintf(stderr, "Konnte keinen neuen binären Baum erzeugen!\n");
    exit(0);
  }
 else
   fprintf(stdout, "Binärbaum konnte erfolgreich initialisiert werden!\n");

 do{
     printf("-1- Neue PLZ hinzufügen\n");
     printf("-2- PLZ suchen\n");
     printf("-3- PLZ löschen\n");
     printf("-4- Ende\n\n");
     printf("Ihre Wahl : ");
     scanf("%d",&wahl);

     if(wahl==1)
      {
       printf("Bitte geben sie eine neue PLZ ein : ");
       scanf("%d",&p);
       printf("Der Ort dazu : ");
       scanf("%s",&o);
       r=einfuegen(re,p,o);
       if(r==0)
        {
         fprintf(stderr, "Fehler beim Speicherallokieren!\n");
         exit(0);
        }
       }
      else if(wahl==2)
        {
          printf("Für welche PLZ suchen sie einen Ort : ");
          scanf("%d",&p);
          binaere_suche_plz(re,p);
         }
      else if(wahl==3)
        {
          printf("Welche PLZ wollen sie löschen : ");
          scanf("%d",&p);
          bin_delete(re,p);
         }
    }while(wahl != 4);

 return 0;
}