fork download
copy 
  1. #include <stdio.h>
  2. #include <conio.h>
  3. #include <Windows.h> 
  4.  
  5.  struct Node {
  6.  
  7.     char s[81];
  8.  
  9.     Node *left, *right;
  10.    Node():left(NULL), right(NULL) {}
  11.    void DestructorWithoutSubTree()
  12.    {
  13.        left = NULL;
  14.        right = NULL;
  15.        delete this;
  16.    }
  17.    ~Node()
  18.    {
  19.        if (left) delete left;
  20.        if (right) delete right;
  21.        left = NULL;
  22.        right = NULL;
  23.    }
  24.  
  25. };
  26.  
  27.  class BTree
  28.  {
  29.      Node* root;
  30.      size_t count;
  31.      void Insert(Node *Tree, char *s)
  32.      {
  33.          if (strcmp(s, Tree->s) >= 0)
  34.          {
  35.              if (!Tree->right)
  36.              {
  37.                  Node *n = new Node;
  38.                  strcpy(n->s, s);
  39.                  Tree->right = n;
  40.              }
  41.              else Insert(Tree->right, s);
  42.          }
  43.          else
  44.          {
  45.              if (!Tree->left)
  46.              {
  47.                  Node *n = new Node;
  48.                  strcpy(n->s, s);
  49.                  Tree->left = n;
  50.              }
  51.              else Insert(Tree->left, s);
  52.          }
  53.      }
  54.  public:
  55.      BTree() :root(NULL),count(0) {};
  56.      ~BTree()
  57.      {
  58.          delete root;
  59.          root = NULL;
  60.          count = 0;
  61.     }
  62.  
  63.      size_t Size()
  64.      {
  65.          return count;
  66.      }
  67.      bool Search(Node *Tree, char *s)
  68.      {
  69.          if (strcmp(s, Tree->s) == 0) return true;
  70.          else if (strcmp(s, Tree->s) > 0)
  71.          {
  72.              if (!Tree->right) return false;
  73.              else return Search(Tree->right, s);
  74.  
  75.          }
  76.          else
  77.          {
  78.              if (!Tree->left) return false;
  79.              else return Search(Tree->left, s);
  80.          }
  81.      }
  82.      bool Search(char *s)
  83.      {
  84.          return Search(root, s);
  85.      }
  86.  
  87.  
  88.      void Insert(char *s)
  89.      {
  90.          if(root)
  91.          Insert(root, s);
  92.          else
  93.          {
  94.              Node *n = new Node;
  95.              strcpy(n->s, s);
  96.              root = n;
  97.          }
  98.          count++;
  99.      }
  100.      Node * FindParent(Node *parent, Node *n)
  101.      {
  102.          if (parent->left == n || parent->right == n) return parent;
  103.          else 
  104.          {
  105.              Node *tmp = new Node;
  106.              tmp = NULL;
  107.              if (parent->left) tmp=FindParent(parent->left, n);
  108.              if (parent->right && !tmp) tmp= FindParent(parent->right, n);
  109.              return tmp;
  110.          }
  111.      }
  112.      Node * FindParent( Node *n)
  113.      {
  114.          return FindParent(root, n);
  115.      }
  116.      void Delete(size_t i)
  117.      {
  118.          Node *n = (*this)[i];
  119.          Node *parent = this->FindParent(n);
  120.  
  121.              if (!n->left && !n->right)
  122.              {
  123.                  if (parent->left == n) parent->left = NULL;
  124.                  if (parent->right == n) parent->right = NULL;
  125.                  if (!parent) root = NULL;
  126.                  delete n;
  127.              }
  128.              else if ((!n->left) != (!n->right))
  129.              {
  130.                  if (parent->left == n)
  131.                  {
  132.                      if(n->left)
  133.                      parent->left = n->left;
  134.                      else parent->left = n->right;
  135.                  }
  136.                  if (parent->right == n) {
  137.                      if (n->left)
  138.                          parent->right = n->left;
  139.                      else parent->right = n->right;
  140.                  }
  141.                  if (!parent) root = n->left ? n->left : n->right;
  142.                  n->DestructorWithoutSubTree();
  143.              }
  144.              else
  145.              {
  146.                  size_t *ptr = new size_t;
  147.                  *ptr = 0;
  148.                  Node *tmp=this->At(n->right,ptr);//Ищем самый левый элемент правого поддерева нашего узла,для того чтобы заменить им удаляемый узел
  149.                  strcpy(n->s, tmp->s);
  150.                  if (n->right == tmp) n->right = tmp->right;//Если самый левый элемент является нашим правым узлом
  151.                  else FindParent(n, tmp)->left = tmp->right;
  152.                  tmp->DestructorWithoutSubTree();
  153.              }
  154.              count--;
  155.  
  156.      }
  157.  
  158.      bool IsEmpty()
  159.      {
  160.          return !root;
  161.      }
  162.      void Show(Node* Tree) {
  163.  
  164.          if (Tree == NULL) return;
  165.          Show(Tree->left);
  166.          printf("\n%s left=%s right=%s",Tree->s,Tree->left->s,Tree->right->s);
  167.          Show(Tree->right);
  168.  
  169.      }
  170.      void Show() {
  171.          Show(root);
  172.          printf("\n");
  173.      }
  174.      void ShowElemAt(size_t i)
  175.      {
  176.          printf("\n%s\n",(*this)[i]->s);
  177.      }
  178.      Node *At(Node *p, size_t *n) {
  179.  
  180.          Node *q;
  181.  
  182.          if (p == NULL) return NULL;
  183.  
  184.          q = At(p->left, n);
  185.  
  186.          if (q != NULL) return q;
  187.  
  188.          if ((*n)-- == 0) return p;
  189.  
  190.          return At(p->right, n);
  191.  
  192.      }
  193.      Node * operator[](size_t n)
  194.      {
  195.          size_t *ptr=new size_t;
  196.          *ptr = n;
  197.          return this->At(root, ptr);
  198.      }
  199.  
  200.  };
  201.  
  202.  
  203.  
  204. int main()
  205. {
  206.     SetConsoleCP(1251);
  207.     SetConsoleOutputCP(1251);
  208.     char ch;
  209.     char buf[81];
  210.     BTree bTree;
  211.     do {
  212.  
  213.         system("cls");
  214.  
  215.         printf("\n1. Добавить строку в дерево\n2. Показать элемент с заданным индексом");
  216.         printf("\n3. Удалить элемент\n4. Проверить есть ли строка в дереве\n5. Вывести все элементы");
  217.         printf("\n6. Очистить дерево\n0. Выход\n");
  218.  
  219.         ch = _getch();
  220.  
  221.         int i;
  222.  
  223.         switch (ch) {
  224.  
  225.         case '1':
  226.             printf("\nВведите строку для добавления(80 символов масимум): ");
  227.             fflush(stdin);
  228.             rewind(stdin);
  229.          if(scanf("%80s", buf) != 1)
  230.             {
  231.                 printf("\nОшибка Ввода");
  232.  
  233.             }
  234.          else bTree.Insert(buf);
  235.             break;
  236.         case '2':
  237.             printf("\nВведите индекс(индекс первого элемента=0) строки которую хотите получить:");
  238.             fflush(stdin);
  239.             rewind(stdin);
  240.             if(scanf("%d", &i)!=1)
  241.             {
  242.                 printf("\nОшибка Ввода\n");
  243.  
  244.             }
  245.             else 
  246.             {
  247.                 if(bTree[i])
  248.                 bTree.ShowElemAt(i);
  249.                 else printf("\nЭлемент с данным индексом отсуствует в списке!\n");
  250.             }
  251.             break;
  252.         case '3':
  253.             printf("\nВведите индекс(индекс первого элемента = 0) строки для удаления: ");
  254.             fflush(stdin);
  255.             rewind(stdin);
  256.             if (scanf("%d", &i) != 1)
  257.             {
  258.                 printf("\nОшибка Ввода\n");
  259.  
  260.             }
  261.             else
  262.             {
  263.                 if (bTree[i])
  264.                 {
  265.                     bTree.Delete(i);
  266.                     printf("\nЭлемент удален\n");
  267.                 }
  268.                 else printf("\nЭлемент с данным индексом отсуствует в списке!\n");
  269.             }
  270.             break;
  271.         case '4':
  272.             printf("\nВведите строку(регистр учитывается): ");
  273.             fflush(stdin);
  274.             rewind(stdin);
  275.             if (scanf("%80s", buf) != 1)
  276.             {
  277.                 printf("\nОшибка Ввода");
  278.  
  279.             }
  280.             else
  281.             {
  282.                 if (bTree.Search(buf)) printf("\nСтрока присутствует в дереве\n");
  283.                 else printf("\nСтрока отсуствует в дереве!\n");
  284.             }
  285.             break;
  286.         case '5':
  287.  
  288.             if (!bTree.IsEmpty()) bTree.Show();
  289.             else  printf("\nДерево пусто\n");
  290.             break;
  291.         case '6':
  292.  
  293.             bTree.~BTree();
  294.             printf("\nСписок очищен\n");
  295.             break;
  296.         case '0':
  297.  
  298.             return 0;
  299.  
  300.         default:
  301.             printf("\nНеизвестная команда,попробуйте еще раз.\n");
  302.             break;
  303.  
  304.         }
  305.  
  306.         system("pause");
  307.  
  308.     } while (1);
  309.     system("PAUSE");
  310.  
  311.  
  312.  
  313.  
  314.  
  315.     return 0;
  316. }
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
prog.cpp:2:19: fatal error: conio.h: No such file or directory
 #include <conio.h>
                   ^
compilation terminated.
stdout
copy 
Standard output is empty
https://ideone.com/LbbHov
language:
C++ (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!