/***************************************************************/
/* Prof. Dr. Carsten Vogt                                      */
/* FH Koeln, Fak. 07 / Nachrichtentechnik                      */
/* http://www.nt.fh-koeln.de/vogt                              */
/*                                                             */
/* Beispielprogramm Nr. 71-73                                  */
/* der frueheren Vorlesung Datenverarbeitung                   */
/*                                                             */
/* Das Programm ermoeglicht Operationen auf einem Suchbaum:    */
/* - Suchen von Elementen (Bsp. 71)                            */
/* - Einfügen von Elementen (Bsp. 72)                          */
/* - Ausfügen von Elementen (Bsp. 73)                          */
/*                                                             */
/* Ausserdem kann der Suchbaum auf den Bildschirm ausgegeben   */
/* werden.                                                     */
/***************************************************************/

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

/**********************************/
/* Typdefinition für Baumelemente */
/**********************************/

typedef struct treeelem {
 int wert;                /* Eintrag des Baumknotens */
 struct treeelem  *left;   /* Zeiger auf li. Sohn */
 struct treeelem  *right;  /* Zeiger auf re. Sohn */
} treeelem;


/****************************************************/
/* Beispiel 71: Suche eines Werts in einem Suchbaum */
/****************************************************/

treeelem *suche(treeelem *baum, int suchwert) {

  /* baum:     zu durchsuchender Baum
     suchwert: zu suchender Wert */

 if (baum==NULL)
  /* Baum leer: Suchwert nicht darin enthalten */
  return NULL;

 if (baum->wert==suchwert)
  /* Suchwert gefunden */
  return baum;

 else if (baum->wert>suchwert)
  /* Suchwert im linken Unterbaum (wenn ueberhaupt) */
   return suche(baum->left,suchwert);

  else  /* Suchwert im rechten Unterbaum (wenn ueberhaupt) */
   return suche(baum->right,suchwert);

}


/********************************************************/
/* Beispiel 72: Einfuegen eines Werts in einem Suchbaum */
/********************************************************/

int insuchbaum(treeelem **baum,int einwert) {

  /* baum:    Baum, in den eingefuegt werden soll
     einwert: einzufuegender Wert */

 if ((*baum)==NULL) {
  /* Blatt erreicht -> Erzeugen und Einfuegen
     eines neuen Elements */
  *baum=(treeelem *) malloc(sizeof(treeelem));
  (*baum)->wert=einwert;
  (*baum)->left=(*baum)->right=NULL;
  return 0; }

 if ((*baum)->wert==einwert)
  /* Wert ist schon im Baum vorhanden */
  return -1;

 else if ((*baum)->wert>einwert)
   /* Einfuegen in den linken Unterbaum */
   return insuchbaum(&((*baum)->left),einwert);

  else
   /* Einfuegen in den rechten Unterbaum */
   return insuchbaum(&((*baum)->right),einwert);

}

/**********************************************************/
/* Beispiel 73:  Ausfuegen eines Werts aus einem Suchbaum */
/**********************************************************/

int del_min(treeelem **baum);
 /* Fuegt Element mit minimalem Eintrag aus einem Baum aus
    und liefert diesen Eintrag zurueck - siehe unten */

int aussuchbaum(treeelem **baum,int auswert) {

 /* baum:    Baum, aus dem ausgefuegt werden soll
    auswert: auszufuegender Wert */

 treeelem *hilf;

 if ((*baum)==NULL)
  /* Wert nicht gefunden */
  return -1;

 if ((*baum)->wert==auswert) {
  /* Wert gefunden */

  if ((*baum)->left==NULL) {
   /* Hochholen des rechten Unterbaums */
   hilf=*baum;
   *baum=(*baum)->right;
   free(hilf);
  }

  else if ((*baum)->right==NULL) {
   /* Hochholen des linken Unterbaums */
   hilf=*baum;
   *baum=(*baum)->left;
   free(hilf);
  }

  else
   /* Hochholen des minimalen Elements aus rechtem Teilbaum */
   (*baum)->wert=del_min(&((*baum)->right));
  return 0;
 }

 else if ((*baum)->wert>auswert)
  /* Suche im linken Unterbaum */
   return aussuchbaum(&((*baum)->left),auswert);

  else /* Suche im rechten Unterbaum */
   return aussuchbaum(&((*baum)->right),auswert);
}

int del_min(treeelem **baum) {

 /* Fuegt Element mit minimalem Eintrag aus einem Baum aus
    und liefert diesen Eintrag zurueck */

 treeelem *hilf;
 int retwert;

 if ((*baum)->left==NULL) {
  /* minimaler Wert gefunden */
  hilf=*baum;
  retwert = (*baum)->wert;
  /* Ausfuegen */
  *baum = (*baum)->right;
  free(hilf);
  return retwert; }

  else /* Fortsetzung der Suche */
   return del_min(&((*baum)->left));

}


/*********************************************/
/* Ausgabe der Baumstruktur als ASCII-Grafik */
/*********************************************/

void drucke_rek(treeelem *baum,
        int left,int top,int right,int bottom) {

 /* baum: auszugebender Baum
    left, top, right, bottom: Teilfenster fuer die Ausgabe
                                 (linke obere und rechte untere Ecke) */
 int i; /* Laufvariable */

 if (baum==NULL)
  /* leerer Baum: nichts zu tun */
  return;

 /* Definition eines Teilfensters */
 window(left,top,right,bottom);

 /* Ausgabe einer senkrechten Kante */
 gotoxy(1+(right-left)/2,1);
 printf(":");
 gotoxy(1+(right-left)/2,2);
 printf(":");

 /* Test, ob linker Unterbaum vorhanden */
 if (baum->left!=NULL) {
  /* Wenn ja: Ausgabe einer Kante, die nach links fuehrt */
  gotoxy((right-left)/4+1,3);
  for (i=(right-left)/4+1;i<(right-left)/2;i++)
   printf("-");
 }

 /* Test, ob rechter Unterbaum vorhanden */
 if (baum->right!=NULL) {
  /* Wenn ja: Ausgabe einer Kante, die nach rechts fuehrt */
  gotoxy((right-left)/2,3);
  for (i=(right-left)/2;i<=1+(3*(right-left))/4;i++)
   printf("-");
 }

 /* Ausgabe des Werts des aktuellen Wurzelknotens */
 gotoxy((right-left)/2,3);
 if (baum->wert<10)
   printf("%2d ",baum->wert);
  else printf("%3d",baum->wert);

 /* rekursive Aufrufe zur Ausgabe des linken und rechten Unterbaums
    in entsprechenden Teilfenstern */
 drucke_rek(baum->left,left,top+3,left+(right-left)/2,bottom);
 drucke_rek(baum->right,left+(right-left)/2+1,top+3,right,bottom);
}

void drucke(treeelem *baum) {
 /* Ausgabe des Gesamtbaums baum mit Hilfe von drucke_rek() */
 clrscr();
 drucke_rek(baum,1,1,80,25);
 window(1,1,80,25);
}


/*****************/
/* Hauptprogramm */
/*****************/

main() {

 treeelem *root=NULL; /* Wurzel des Baums */
 treeelem *eintrag;   /* Hilfszeiger auf Baumeintrag */
 int wert;            /* Einzufuegender, auszufuegender bzw. gesuchter Wert */
 int err;             /* Fehlercode */
 char choice;         /* zur Auswahl einer Funktion */

 do {

  printf("Bitte waehlen:\n");
  printf(" e: Einfuegen eines Werts\n");
  printf(" a: Ausfuegen eines Werts\n");
  printf(" s: Suchen eines Werts\n");
  printf(" u: Ausgabe des Suchbaums\n");
  printf(" q: Beenden des Programms\n");

  fflush(stdin);
  scanf("%c",&choice);
  printf("\n");

  switch(choice) {

   case 'e': printf("Bitte einzufuegenden Wert eingeben: ");
             scanf("%d",&wert);
             err=insuchbaum(&root,wert);
             if (err==0)
               printf("Ok\n\n");
              else printf("Wert im Baum schon vorhanden\n\n");
             break;

   case 'a': printf("Bitte auszufuegenden Wert eingeben: ");
             scanf("%d",&wert);
             err=aussuchbaum(&root,wert);
             if (err==0)
               printf("Ok\n\n");
              else printf("Wert im Baum nicht vorhanden\n\n");
             break;

   case 's': printf("Bitte zu suchenden Wert eingeben: ");
             scanf("%d",&wert);
             eintrag=suche(root,wert);
             if (eintrag!=NULL)
               printf("Eintrag gefunden!\n\n");
              else printf("Eintrag nicht gefunden!\n\n");
             break;

   case 'u': drucke(root);
             getch();
             clrscr();
             break;
  }

 } while (choice!='q');

}