#include <stdio.h>
#include <string.h>
#include <conio.h>
#include <locale.h>

enum Commands
{
   CMD_INDIS = 1,
   CMD_OUT, CMD_DELMIN, CMD_DELMAX, CMD_PREOR, CMD_INORD, CMD_POSTOR, CMD_EXIT
};

struct tree
{
   char elem;
   tree *left, *right;

   tree(char _el = '%', tree *_left = NULL, tree *_right = NULL) :
      elem(_el), left(_left), right(_right) {}
};

const int Nmax = 100;

void input(char s[Nmax]);
void create(tree *&t, char b[Nmax]);
void insert(tree **t, char c);
void createRec(tree *&t, char b[Nmax]);
void insertRec(tree *&t, char c);
void delMax(tree *&t);
void delMin(tree *&t);
void preor(tree *t);
void inor(tree *t);
void postor(tree *t);

int main()
{
   setlocale(LC_CTYPE, "Russian");
   tree *t = NULL;
   char s[Nmax];

   input(s);

   int exitFlag = 0, n = 0;
   do
   {
      printf_s("1. Создать дерево итеративным методом  \n");
      printf_s("2. Создать дерево рекурсивным методом  \n");
      printf_s("3. Удалить минимальный элемент дерева  \n");
      printf_s("4. Удалить максимальный элемент дерева  \n");
      printf_s("5. Распечатать дерево в прямом порядке  \n");
      printf_s("6. Распечатать дерево в обратном порядке  \n");
      printf_s("7. Распечатать дерево в концевом порядке  \n");
      printf_s("8. Выход из программы  \n");
      int repeatFlag = 0;
      do
      {
         printf_s("Введите номер команды (от 1 до 8): ");
         if (!scanf_s("%d", &n))
         {
            printf_s("ошибка ввода");
            _getch();
         }
         switch (n)
         {
            case CMD_INDIS:
               create(t, s);
               break;

            case CMD_OUT:
               createRec(t, s);
               break;

            case CMD_DELMIN:
               if (t)
               {
                  delMin(t);
                  break;
               }
               printf("Сначала создайте дерево\n");
               break;

            case CMD_DELMAX:
               if (t)
               {
                  delMax(t);
                  break;
               }
               printf("Сначала создайте дерево\n");
               break;

            case CMD_PREOR:
               if (t)
               {
                  preor(t);
                  printf("\n");
                  break;
               }
               printf("Сначала создайте дерево\n");
               break;

            case CMD_INORD:
               if (t)
               {
                  inor(t);
                  printf("\n");
                  break;
               }
               printf("Сначала создайте дерево\n");
               break;

            case CMD_POSTOR:
               if (t)
               {
                  postor(t);
                  printf("\n");
                  break;
               }
               printf("Сначала создайте дерево\n");
               break;

            case CMD_EXIT: exitFlag = 1;
               break;

            default: printf_s("Ошибка: неверный номер команды\n");
               repeatFlag = 1;
         }
      } while (!repeatFlag && !exitFlag);
   } while (!exitFlag);

   return 0;
}

void input(char s[Nmax])
{
   FILE *f;
   fopen_s(&f, "in.txt", "r");
   fgets(s, Nmax, f);
   fclose(f);
}

void create(tree *&t, char b[Nmax])
{
   int len = strlen(b);
   for (int i = 0; i < len; i++)
      insert(&t, b[i]);
}

void insert(tree **t, char c)
{
   tree **w = t;
   while (*w)
      w = c < (*w)->elem ? &(*w)->left : &(*w)->right;
   *w = new tree(c);
}

void createRec(tree *&t, char b[Nmax])
{
   int len = strlen(b);
   for (int i = 0; i < len; i++)
      insertRec(t, b[i]);
}

void insertRec(tree *&t, char c)
{
   if (t)
      c < t->elem ? insertRec(t->left, c) : insertRec(t->right, c);
   else
      t = new tree(c);
}

void delMin(tree *&t)
{
   tree *a = t, *b;
   for (b = t; b->left; b = b->left)
      a = b;
   a->left = b->right;
}

void delMax(tree *&t)
{
   tree *a = t, *b;
   for (b = t; b->right; b = b->right)
      a = b;
   a->right = b->left;
}

void preor(tree *t)
{
   printf("%c", t->elem);
   if (t->left)
      preor(t->left);
   if (t->right)
      preor(t->right);
}

void inor(tree *t)
{
   if (t->left)
      inor(t->left);
   printf("%c", t->elem);
   if (t->right)
      inor(t->right);
}

void postor(tree *t)
{
   if (t->left)
      postor(t->left);
   if (t->right)
      postor(t->right);
   printf("%c", t->elem);
}