SHARE
TWEET

Untitled

a guest May 21st, 2019 97 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdio.h>
  2. #include <string.h>
  3. #include <conio.h>
  4. #include <locale.h>
  5.  
  6. enum Commands
  7. {
  8.    CMD_INDIS = 1,
  9.    CMD_OUT, CMD_DELMIN, CMD_DELMAX, CMD_PREOR, CMD_INORD, CMD_POSTOR, CMD_EXIT
  10. };
  11.  
  12. struct tree
  13. {
  14.    char elem;
  15.    tree *left, *right;
  16.  
  17.    tree(char _el = '%', tree *_left = NULL, tree *_right = NULL) :
  18.       elem(_el), left(_left), right(_right) {}
  19. };
  20.  
  21. const int Nmax = 100;
  22.  
  23. void input(char s[Nmax]);
  24. void create(tree *&t, char b[Nmax]);
  25. void insert(tree **t, char c);
  26. void createRec(tree *&t, char b[Nmax]);
  27. void insertRec(tree *&t, char c);
  28. void delMax(tree *&t);
  29. void delMin(tree *&t);
  30. void preor(tree *t);
  31. void inor(tree *t);
  32. void postor(tree *t);
  33.  
  34. int main()
  35. {
  36.    setlocale(LC_CTYPE, "Russian");
  37.    tree *t = NULL;
  38.    char s[Nmax];
  39.  
  40.    input(s);
  41.  
  42.    int exitFlag = 0, n = 0;
  43.    do
  44.    {
  45.       printf_s("1. Создать дерево итеративным методом  \n");
  46.       printf_s("2. Создать дерево рекурсивным методом  \n");
  47.       printf_s("3. Удалить минимальный элемент дерева  \n");
  48.       printf_s("4. Удалить максимальный элемент дерева  \n");
  49.       printf_s("5. Распечатать дерево в прямом порядке  \n");
  50.       printf_s("6. Распечатать дерево в обратном порядке  \n");
  51.       printf_s("7. Распечатать дерево в концевом порядке  \n");
  52.       printf_s("8. Выход из программы  \n");
  53.       int repeatFlag = 0;
  54.       do
  55.       {
  56.          printf_s("Введите номер команды (от 1 до 8): ");
  57.          if (!scanf_s("%d", &n))
  58.          {
  59.             printf_s("ошибка ввода");
  60.             _getch();
  61.          }
  62.          switch (n)
  63.          {
  64.             case CMD_INDIS:
  65.                create(t, s);
  66.                break;
  67.  
  68.             case CMD_OUT:
  69.                createRec(t, s);
  70.                break;
  71.  
  72.             case CMD_DELMIN:
  73.                if (t)
  74.                {
  75.                   delMin(t);
  76.                   break;
  77.                }
  78.                printf("Сначала создайте дерево\n");
  79.                break;
  80.  
  81.             case CMD_DELMAX:
  82.                if (t)
  83.                {
  84.                   delMax(t);
  85.                   break;
  86.                }
  87.                printf("Сначала создайте дерево\n");
  88.                break;
  89.  
  90.             case CMD_PREOR:
  91.                if (t)
  92.                {
  93.                   preor(t);
  94.                   printf("\n");
  95.                   break;
  96.                }
  97.                printf("Сначала создайте дерево\n");
  98.                break;
  99.  
  100.             case CMD_INORD:
  101.                if (t)
  102.                {
  103.                   inor(t);
  104.                   printf("\n");
  105.                   break;
  106.                }
  107.                printf("Сначала создайте дерево\n");
  108.                break;
  109.  
  110.             case CMD_POSTOR:
  111.                if (t)
  112.                {
  113.                   postor(t);
  114.                   printf("\n");
  115.                   break;
  116.                }
  117.                printf("Сначала создайте дерево\n");
  118.                break;
  119.  
  120.             case CMD_EXIT: exitFlag = 1;
  121.                break;
  122.  
  123.             default: printf_s("Ошибка: неверный номер команды\n");
  124.                repeatFlag = 1;
  125.          }
  126.       } while (!repeatFlag && !exitFlag);
  127.    } while (!exitFlag);
  128.  
  129.    return 0;
  130. }
  131.  
  132. void input(char s[Nmax])
  133. {
  134.    FILE *f;
  135.    fopen_s(&f, "in.txt", "r");
  136.    fgets(s, Nmax, f);
  137.    fclose(f);
  138. }
  139.  
  140. void create(tree *&t, char b[Nmax])
  141. {
  142.    int len = strlen(b);
  143.    for (int i = 0; i < len; i++)
  144.       insert(&t, b[i]);
  145. }
  146.  
  147. void insert(tree **t, char c)
  148. {
  149.    tree **w = t;
  150.    while (*w)
  151.       w = c < (*w)->elem ? &(*w)->left : &(*w)->right;
  152.    *w = new tree(c);
  153. }
  154.  
  155. void createRec(tree *&t, char b[Nmax])
  156. {
  157.    int len = strlen(b);
  158.    for (int i = 0; i < len; i++)
  159.       insertRec(t, b[i]);
  160. }
  161.  
  162. void insertRec(tree *&t, char c)
  163. {
  164.    if (t)
  165.       c < t->elem ? insertRec(t->left, c) : insertRec(t->right, c);
  166.    else
  167.       t = new tree(c);
  168. }
  169.  
  170. void delMin(tree *&t)
  171. {
  172.    tree *a = t, *b;
  173.    for (b = t; b->left; b = b->left)
  174.       a = b;
  175.    a->left = b->right;
  176. }
  177.  
  178. void delMax(tree *&t)
  179. {
  180.    tree *a = t, *b;
  181.    for (b = t; b->right; b = b->right)
  182.       a = b;
  183.    a->right = b->left;
  184. }
  185.  
  186. void preor(tree *t)
  187. {
  188.    printf("%c", t->elem);
  189.    if (t->left)
  190.       preor(t->left);
  191.    if (t->right)
  192.       preor(t->right);
  193. }
  194.  
  195. void inor(tree *t)
  196. {
  197.    if (t->left)
  198.       inor(t->left);
  199.    printf("%c", t->elem);
  200.    if (t->right)
  201.       inor(t->right);
  202. }
  203.  
  204. void postor(tree *t)
  205. {
  206.    if (t->left)
  207.       postor(t->left);
  208.    if (t->right)
  209.       postor(t->right);
  210.    printf("%c", t->elem);
  211. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top