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

#define MAX_LENGTH 100

struct bbaum {
  char name[MAX_LENGTH];
  struct bbaum *left;
  struct bbaum *right;
};

int speichern (struct bbaum *baum, FILE *fp) {
  if (baum == NULL){
  /* Nichts zu tun */
    return 0;
  } else {
    fprintf(fp, "%s",baum->name);
    speichern(baum->left, fp);
    speichern(baum->right, fp);
  }
  return 0;
}


int einfuegen (struct bbaum **baum, char *wert) {
  if ((*baum) == NULL) {
    /* Blatt erreicht -> Einfuegen */
    *baum = (struct bbaum *) malloc(sizeof(struct bbaum));
    strcpy((*baum)->name, wert);
    (*baum)->left = NULL;
    (*baum)->right = NULL;
    return 0;
  }

  if(!strcmp((*baum)->name, wert)){
    /* Name ist schon vorhanden */
    return -1;
  }
  
  if(strcmp((*baum)->name, wert) < 0) {
    /* In den linken Ast einfuegen */
    return einfuegen (&((*baum)->left), wert);
  } else{
    /* In den rechten Ast einfuegen */
    return einfuegen (&((*baum)->right), wert);
  }
}


int laden (struct bbaum **root,FILE *fp) {
  int err;
  char wert[MAX_LENGTH];
  /* So lange lesen, bis EOF */
  while (fgets(wert, MAX_LENGTH, fp) != NULL) {
    err = einfuegen(root, wert);
  };
  return 0;
}


void drucke(struct bbaum *baum, int level){
  int i;
  
  if( baum == NULL) {
    /* Baum leer, nichts zu tun */
    return;
  }
  drucke(baum->left, level+1);
  for(i = 0 ; i <=level ; i++) printf("   ");
  printf ("%s",baum->name);
  drucke(baum->right, level +1);
}
  

void preorder(struct bbaum *baum) {
  if (baum == NULL) {
    return;
  }
  printf("%s ",baum->name);
  if (baum->right != NULL) {
    preorder(baum->right);
  }
  if (baum->left != NULL) {
    preorder(baum->left);
  }
}

void postorder(struct bbaum *baum) {
  if(baum->right != NULL) {
    postorder(baum->right);
  }
  if (baum->left != NULL) {
   postorder(baum->left);
  }
  printf("%s ", baum->name);
}

void inorder(struct bbaum *baum) {
  if (baum->right != NULL) {
    inorder(baum->right);
  }
    printf("%s ",baum->name);
  if(baum->left != NULL) {
    inorder(baum->left);
  }
}



int main() {
  struct bbaum *root = NULL;
  
  char wert[100];
  int err;
  FILE *fp;
  char choice;

  do {
    printf("Bitte Waehlen:\n");
    printf("  'e' : Einfuegen eines Namens\n");
    printf("  'q' : Programm beenden\n");
    printf("  'a' : Baum ausgeben\n");
    printf("  's' : Baum speichern\n");
    printf("  'l' : Baum laden\n");
    printf("  'p' : Baum tarversieren Preorder\n");
    printf("  'o' : Baum traversieren Postorder\n");
    printf("  'i' : Baum traversieren Inorder\n");
    choice = getchar();
    while (getchar() != '\n');
     printf("\n");

    switch (choice) {
       case 'e' : printf("Bitte Wort eingeben\n");
                  fgets(wert, 499, stdin);
	          wert[strlen(wert)-1]='\n';
	          wert[strlen(wert)]='\0';
	          err = einfuegen (&root, wert);
	          if (err){
	             printf("Wort schon vorhanden\n");
	          }else{
	             printf("Alles in Ordnung\n");
	          }
	          break;

      case 'a' : drucke(root,0);
                 break;
      case 's' : fp = fopen("DATEN","w");
                 if(fp == NULL) {
		   perror("fopen");
		 }else{
		   speichern(root, fp);
		   fclose(fp);
		 }
		 break;
      case 'l' : fp = fopen("DATEN","r");
                 if(fp == NULL) {
		   perror("fopen");
		 }else{
		   laden(&root, fp);
		   fclose(fp);
	 	 }
		 break;
     case 'p'  : preorder(root);
                 break;
     case 'o'  : postorder(root);
                 break;
     case 'i'  : inorder(root);
                 break;
    }
 }while (choice != 'q');

 return 0;
}