/*********************************/
/* BINTREE: Ein binärer Suchbaum */
/*-------------------------------*/
/*   by Dirk Owerfeldt & MAXON   */
/*********************************/


/*----------*/
/* Includes */
/*----------*/

#include <exec/types.h>
#include <stdio.h>


#define REG register
#define CHAR char
#define BOOLEAN BOOL

#define CLS   fputchar ( 0xc );
#define TASTE printf("-- Return --"); gets( hilf )

CHAR hilf[50];


/*-------------------*/
/* Die Datenstruktur */
/*-------------------*/

typedef struct TREE
{
   WORD info;

   struct TREE *left,*right;
} TREE;

TREE *root;


/*----------------------------------------*/
/* Fügt ein neues Element in den Baum ein */
/*----------------------------------------*/

TREE *insert(tree,info)
TREE *tree;
WORD info;
{
   if(tree==NULL)
   {
      tree=(TREE *) malloc(sizeof (struct TREE));
      tree->info=info;
      tree->left=NULL;
      tree->right=NULL;
   }
   else
   {
      if(info<tree->info) tree->left=insert(tree->left,info); else
      if(info>tree->info) tree->right=insert(tree->right,info); 
   }

   return tree;
}

/*------------------------*/
/* Die drei Ausgabefolgen */
/*------------------------*/

VOID preorder(tree)
TREE *tree;
{
   if(tree!=NULL)
   {
      printf("%d\n",tree->info);

      preorder(tree->left);
      preorder(tree->right);
   }
}

VOID inorder(tree)
TREE *tree;
{
   if(tree!=NULL)
   {
      inorder(tree->left);
      printf("%d\n",tree->info);
      inorder(tree->right);
   }
}

VOID postorder(tree)
TREE *tree;
{
   if(tree!=NULL)
   {
      postorder(tree->left);
      postorder(tree->right);

      printf("%d\n",tree->info);
   }
}

/*-----------------------------*/
/* Ausgabe des Baumes als Baum */
/*-----------------------------*/

VOID printtree(tree)
TREE *tree;
{
   WORD i;
   static tab=0;

   if(tree!=NULL)
   {
      tab+=6;
      printtree(tree->right);
      for(i=6;i<tab;i++) printf(" ");
      printf("%6d\n",tree->info);
      printtree(tree->left);
      tab-=6;
   }
}

/*-----------------*/
/* Rekursive Suche */
/*-----------------*/

TREE *suche(tree,nr)
TREE *tree;
WORD nr;
{
   if(tree==NULL)
      return NULL;
   else
   {
      if(nr==tree->info) return(tree);
      if(nr<tree->info) return(suche(tree->left,nr));
      if(nr>tree->info) return(suche(tree->right,nr)); 
   }
}

/*-----------------*/
/* iterative Suche */
/*-----------------*/

TREE *i_suche(tree,nr)
TREE *tree;
WORD nr;
{
   while( (tree!=NULL) && (tree->info!=nr) )
   {
      if(nr<tree->info) tree=tree->left; else
      if(nr>tree->info) tree=tree->right;
   }

   return(tree);
}

/***************************/
/* Löschen eines Elementes */
/***************************/

/*--------------------------*/
/* Hilfsfunktion: pp-search */
/*--------------------------*/

TREE **s_search(pp,info)
TREE **pp;
{
   TREE **qq;

   qq=pp;

   while(*qq!=NULL && info != (*qq)->info)
   {
      if(info<(*qq)->info) qq = &(*qq)->left; 
      else                 qq = &(*qq)->right;
   }
    
/*  
      qq = (info < (*qq)->info ? &(*qq)->left : &(*qq)->right);
*/

   return qq;
}

 
/*-------------------------------*/
/* Die eigentliche Löschfunktion */
/*-------------------------------*/

VOID loesche(pp)
TREE **pp;
{
   TREE *p,**qq,*q;

   if(*pp!=NULL)
   {
      p = *pp;

      if (p->right==NULL) { *pp  = p->left; free(p);  } else
      if (p->left ==NULL) { *pp  = p->right; free(p); } else
      {
         qq = & p->left;

         while( (*qq)->right != NULL ) 
            qq = & (*qq)->right;

         q = *qq;
         *qq = q->left;
         
         p->info = q->info;
         free(q);
      }
   }
}

/*---------------------------------------*/
/* Perfekt ausbalancierten Baum erzeugen */
/*---------------------------------------*/

WORD Num;

TREE *pb_tree(n)
WORD n;
{
   WORD nleft,nright;
   TREE *p;

   if(n==0) return NULL;

   nleft  = n / 2;
   nright = n - nleft -1;

   p = (TREE *) malloc(sizeof(TREE));
   
   p->left = pb_tree(nleft);
   p->info = Num; Num+=(UWORD) rand() % 20;
   p->right= pb_tree(nright);
  
   return p;
}


/*-------------------*/
/* Das Hauptprogramm */
/*-------------------*/

VOID main( VOID )
{
   BOOLEAN  schleife=TRUE;
   WORD     i,z;
   CHAR     c[80],zahl[80];
   TREE     *s,**ss;

   /*----------------------*/
   /* Liste initialisieren */
   /*----------------------*/

   root = NULL;

   CLS;

   printf("Baum intialisieren?\n\n");
   printf("1) Perfekt ausgeglichener Baum\n");
   printf("2) Zufällig erzeugter Baum\n");
   printf("3) Keine Initialisierung\n");

   printf("\n>");
   gets(c);

   if(c[0]!='3')
   {
      printf("Zahl der Elemente (1-15): "); gets(zahl);
      
      switch( c[0] )
      {
         case '1':
                   Num=rand() % 100;
                   root=pb_tree(atoi(zahl));
                   break;

         case '2': 
                   root=insert(root,250);
                   for(i=1;i<atoi(zahl);i++)
                        root=insert(root,(UWORD) rand() % 500);                          
                   break;
      }
   }


   /*-----------*/
   /* Hauptmenü */
   /*-----------*/

   while(schleife)
    {
      CLS;

      printf("** Ein binärer Suchbaum / by Dirk Owerfeldt **\n\n");

      printtree(root);

      printf("Menü:\n\n");
      printf("1) Element hinzufügen      4) Preorder -Ausgabe\n");
      printf("2) Element löschen         5) Inorder  -Ausgabe\n");
      printf("3) Element suchen          6) Postorder-Ausgabe\n");
      printf("9) Ende               >");

      gets(c); printf("\n\n");

      switch( c[0] )
      {
        case '1': 
                  printf("Eingabe (0=Ende)\n");

                  do{ 
                      gets(zahl);
                      if((z=atoi(zahl))!=0)
                         root=insert(root,z);
                  }while(z!=0);
                  break;

        case '2': 
                  printf("Zu löschendes Element: ");

                  gets(zahl);
                  ss=s_search(&root,atoi(zahl));
                  if(*ss==NULL)
                  {
                     puts("Element nicht vorhanden !!");
                     TASTE; 
                  }
                  else
                     loesche(ss);
                  break;

        case '3':
                  printf("Gesuchtes Element: ");

                  gets(zahl);
      
                  if((s=suche(root,atoi(zahl)))==NULL) 
                  {
                     puts("Element nicht vorhanden !!");
                     TASTE;
                  }
                  else
                  {
                     printf("Zahl %d vorhanden!\n",s->info);
                     TASTE;
                  }
                  break;

        case '4': printf("Preorder-Sequenz:\n\n");
                  preorder(root);
                  TASTE;
                  break;

        case '5': printf("Inorder-Sequenz:\n\n"); 
                  inorder(root);
                  TASTE;
                  break;

        case '6': printf("Postorder-Sequenz:\n\n"); 
                  postorder(root);
                  TASTE;
                  break; 

        case '9': schleife=FALSE;
                  break;
      }
   }
}