/***************************************************************/
/* Prof. Dr. Carsten Vogt                                      */
/* FH Koeln, Fak. 07 / Nachrichtentechnik                      */
/* http://www.nt.fh-koeln.de/vogt                              */
/*                                                             */
/* Beispielprogramm p08040200.c                                */
/* aus "C fuer Java-Programmierer", Hanser-Verlag              */
/*                                                             */
/* Demonstriert wird der Umgang mit Binärbäumen.               */
/***************************************************************/

#define INORDER   0
#define PREORDER  1
#define POSTORDER 2

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

typedef struct binbaumknoten {
  char *wert;
  struct binbaumknoten *li_sohn;
  struct binbaumknoten *re_sohn;
} binbaumknoten;

binbaumknoten *wurzel_strukturbaum = NULL,
              *wurzel_suchbaum = NULL,
              *gewaehlter_baum;
              
char string[40];

int result;

/* Erzeugung eines neuen Knotens mit einem bestimmten Wert */

binbaumknoten *neuer_knoten(char *wert) {
 binbaumknoten *kn;
 kn = (binbaumknoten *) malloc(sizeof(binbaumknoten));
 if (kn==NULL)
  return NULL;
 kn->wert = (char *) malloc(40);
 if (kn->wert == NULL ) {
   free(kn);
   return(NULL);            
  }
 strcpy(kn->wert,wert);
 kn->li_sohn = kn->re_sohn = NULL;
 return kn;             
}

/* Erzeugung des Beispiel-Strukturbaums */

char *eintraege[] = { "-", "*", "+", "+", "5", "2", "1", "3", "4", " ", " ", " ", " ", " ", " ", " ", " ", " ", " "  };

binbaumknoten *erzeuge_beispielstrukturbaum(unsigned int index) {
 binbaumknoten *kn;
 if (strcmp(eintraege[index]," ")==0)
  return NULL;
 kn = neuer_knoten(eintraege[index]);
 kn->li_sohn = erzeuge_beispielstrukturbaum(2*index+1);   
 kn->re_sohn = erzeuge_beispielstrukturbaum(2*index+2);
 return kn;   
}

/* Ausgeben des Bauminhalts in einer Zeile gemaess Inorder, Preorder oder Postorder */

void ausgeben(binbaumknoten *knoten, int order) {
 if (knoten==NULL)
  return;
 switch(order) {
  case INORDER:
   ausgeben(knoten->li_sohn,INORDER);
   printf("%s ",knoten->wert);
   ausgeben(knoten->re_sohn,INORDER);
   break;
  case PREORDER:
   printf("%s ",knoten->wert);
   ausgeben(knoten->li_sohn,PREORDER);
   ausgeben(knoten->re_sohn,PREORDER);
   break;
  case POSTORDER:
   ausgeben(knoten->li_sohn,POSTORDER);
   ausgeben(knoten->re_sohn,POSTORDER);
   printf("%s ",knoten->wert);
   break;
  }
}

/* Ausgeben des Bauminhalts in mehreren Zeilen, wodurch die Baumstruktur zumindest angedeutet wird */

#define TAB 4

void ausgeben_strukturiert(binbaumknoten *knoten, int einrueck) {
 int i;
 if (knoten==NULL)
  return;
 ausgeben_strukturiert(knoten->re_sohn,einrueck+1);
 for (i=1;i<=einrueck*TAB;i++)
  printf(" ");
 printf("%s\n",knoten->wert);
 ausgeben_strukturiert(knoten->li_sohn,einrueck+1);
}

/* Einfuegen einer Zeichenkette in einen Suchbaum */

int einfuegen(binbaumknoten **knoten, char *neuerwert) {
 if ((*knoten)==NULL) {
   *knoten = (binbaumknoten *) malloc(sizeof(binbaumknoten));
   (*knoten)->wert = (char *) malloc(strlen(neuerwert)+1);
   strcpy((*knoten)->wert,neuerwert);
   (*knoten)->li_sohn = (*knoten)->re_sohn = NULL;
   return 0;
  }
 if (strcmp((*knoten)->wert,neuerwert)==0)
   return -1;
 else
  if (strcmp((*knoten)->wert,neuerwert)>0)
    return einfuegen(&((*knoten)->li_sohn),neuerwert);
   else
    return einfuegen(&((*knoten)->re_sohn),neuerwert);
}

/* Suchen einer Zeichenkette in einem Suchbaum */

binbaumknoten *suchen(binbaumknoten *knoten, char *gesucht) {
 if (knoten==NULL)
  return NULL;
 if (strcmp(knoten->wert,gesucht)==0)
    return knoten;
  else
   if (strcmp(knoten->wert,gesucht)>0)
     return suchen(knoten->li_sohn,gesucht);
    else
     return suchen(knoten->re_sohn,gesucht);
}

/* Loeschen einer Zeichenkette aus einem Suchbaum */

binbaumknoten *loeschen_min(binbaumknoten **knoten) {
 binbaumknoten *minknoten;
 if ((*knoten)->li_sohn==NULL) {
    minknoten=*knoten;
    *knoten=(*knoten)->re_sohn;
    return minknoten;
   }
  else
   return loeschen_min(&((*knoten)->li_sohn));
}

int loeschen(binbaumknoten **knoten, char *zuloeschen) {
 binbaumknoten *kn;
 if (knoten==NULL||(*knoten)==NULL)
   return -1;
 if (strcmp((*knoten)->wert,zuloeschen)==0) {
   if ((*knoten)->li_sohn==NULL) {
    kn=*knoten;
    *knoten=(*knoten)->re_sohn;
    free(kn->wert);
    free(kn);
   }
   else if ((*knoten)->re_sohn==NULL) {
    kn=*knoten;
    *knoten=(*knoten)->li_sohn;
    free(kn->wert);
    free(kn);
   }
   else {
    kn=loeschen_min(&((*knoten)->re_sohn));
    strcpy((*knoten)->wert,kn->wert);
    free(kn->wert);
    free(kn);
   }
   return 0;
  }
 if (strcmp((*knoten)->wert,zuloeschen)>0)
   return loeschen(&((*knoten)->li_sohn),zuloeschen);
  else
   return loeschen(&((*knoten)->re_sohn),zuloeschen);
}

/* Loeschen eines Binaerbaums */

void loeschen_baum(binbaumknoten **knoten) {
 if ((*knoten)==NULL)
  return;
 loeschen_baum(&((*knoten)->li_sohn));
 loeschen_baum(&((*knoten)->re_sohn));
 free((*knoten)->wert);
 free(*knoten);
 *knoten=NULL;
}

/* Hauptprogramm */

int main(void) {

 int wahl, wahl2, wahlbaum;
 
 wurzel_strukturbaum = erzeuge_beispielstrukturbaum(0);

 do {

  do {

   printf("\nBitte Funktion auswaehlen:\n\n");
   printf("( 1 )  Baum anzeigen\n");
   printf("( 2 )  in Suchbaum einfuegen\n");
   printf("( 3 )  aus Suchbaum entfernen\n");
   printf("( 4 )  in Suchbaum suchen\n");
   printf("( 5 )  Baum loeschen\n");
   printf("( 0 )  Programmende\n");

   scanf("%d",&wahl);

  } while (wahl<0 || wahl>5);

  printf("\n");

  switch(wahl) {

   case 1:

    do {
     printf("\nBitte anzuzeigenden Baum auswaehlen:\n\n");
     printf("( 1 )  Strukturbaum\n");
     printf("( 2 )  Suchbaum\n");
     scanf("%d",&wahlbaum);
    } while (wahlbaum<1 || wahlbaum>2);
    
    if (wahlbaum==1)
      gewaehlter_baum = wurzel_strukturbaum;
     else
      gewaehlter_baum = wurzel_suchbaum;

    do {
     printf("\nBitte Art der Anzeige auswaehlen:\n\n");
     printf("( 1 )  Inorder\n");
     printf("( 2 )  Preorder\n");
     printf("( 3 )  Postorder\n");
     printf("( 4 )  zeilenweise strukturiert\n");
     scanf("%d",&wahl2);
    } while (wahl2<1 || wahl2>4);
    
    switch(wahl2) {
     case 1: ausgeben(gewaehlter_baum,INORDER); break;              
     case 2: ausgeben(gewaehlter_baum,PREORDER); break;              
     case 3: ausgeben(gewaehlter_baum,POSTORDER); break;              
     case 4: ausgeben_strukturiert(gewaehlter_baum,0); break;              
    }

    break;

  case 2:

    printf("\neinzufuegende Zeichenkette: ");
    fflush(stdin);
    scanf("%s",string);

    result = einfuegen(&wurzel_suchbaum,string);

    if (result==0)
      printf("\nEinfuegen erfolgreich\n\n");
     else
      printf("\nEinfuegen fehlgeschlagen: Wert bereits im Baum\n\n");

    break;

   case 3:

    printf("\nzu loeschende Zeichenkette: ");
    fflush(stdin);
    scanf("%s",string);

    result = loeschen(&wurzel_suchbaum,string);

    if (result==0)
      printf("\nLoeschen erfolgreich\n\n");
     else
      printf("\nLoeschen fehlgeschlagen: Wert nicht im Baum\n\n");

    break;

   case 4:

    printf("\ngesuchte Zeichenkette: ");
    fflush(stdin);
    scanf("%s",string);

    if (suchen(wurzel_suchbaum,string)!=NULL)
      printf("\ngefunden\n\n");
     else
      printf("\nnicht gefunden\n\n");

    break;

   case 5:

    do {
     printf("\nBitte zu loeschenden Baum auswaehlen:\n\n");
     printf("( 1 )  Strukturbaum\n");
     printf("( 2 )  Suchbaum\n");
     scanf("%d",&wahlbaum);
    } while (wahlbaum<1 || wahlbaum>2);
    
    if (wahlbaum==1)
      loeschen_baum(&wurzel_strukturbaum);
     else
      loeschen_baum(&wurzel_suchbaum);

    break;

  }

 } while (wahl!=0);

 return 0;

}