AlexandrTalchuk

Untitled

May 8th, 2021
709
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<iostream>
  2. #include"conio.h"
  3. using namespace std;
  4.  
  5. struct Tree
  6. {
  7.     int number;
  8.     char* FIO;
  9.     Tree* left, * right;
  10. };
  11.  
  12. void Add(Tree*& root, int num, char* fio);
  13. void Prefiks(Tree*& node);
  14. void Infiks(Tree*& node);
  15. void Postfiks(Tree*& node);
  16. void SearchbyKey(Tree*& node);
  17. void Balance(Tree*& p, Tree** arr, int n, int k);
  18. void Clear(Tree*& p);
  19. void Solution(Tree* r, int& value, int& counter);
  20. Tree* Delete(Tree* node, int inf);
  21. void closestNode(Tree*& root, int sredn, Tree*&);
  22.  
  23.  
  24. int main()
  25. {
  26.     setlocale(LC_ALL, "rus");
  27.     int choice, num, count = 0, t = 0, key = 0, value = 0, counter = 0, srdn = 0;
  28.     char fio[36];
  29.     Tree* root = nullptr;
  30.     Tree* result = nullptr;
  31.     Tree** arr = new Tree * [count];
  32.     while (true)
  33.     {
  34.         cout << "1.Добавить элемент в дерево\n2.Найти элемент по ключу\n3.Удалить элемент по ключу\n4.Сбалансировать дерево\n5.Префиксный просмотр (сверху вниз)\n6.Инфиксный просмотр (слева направо)\n7.Постфиксный просмотр (снизу вверх)\n8.Задание\n9.Выход" << endl;
  35.         cin >> choice;
  36.         switch (choice)
  37.         {
  38.         case 1:
  39.             cout << "Введите ФИО: ";
  40.             cin.ignore();
  41.             cin.getline(fio, 36);
  42.             cout << "Введите номер: ";
  43.             cin >> num;
  44.             Add(root, num, fio);
  45.             break;
  46.         case 2:
  47.             SearchbyKey(root);
  48.             _getch();
  49.             break;
  50.         case 3:
  51.             cout << "Введите ключ";
  52.             cin >> key;
  53.             Delete(root, key);
  54.             break;
  55.         case 4:
  56.             Balance(root, arr, 0, count);
  57.             cout << "Дерево сбалансированно" << endl;
  58.             _getch();
  59.         case 5:
  60.             if (root == NULL)
  61.             {
  62.                 cout << "Дерево пустое" << endl;
  63.             }
  64.             Prefiks(root);
  65.             _getch();
  66.             break;
  67.         case 6:
  68.             if (root == NULL)
  69.             {
  70.                 cout << "Дерево пустое" << endl;
  71.             }
  72.             Infiks(root);
  73.             _getch();
  74.             break;
  75.         case 7:
  76.             if (root == NULL)
  77.             {
  78.                 cout << "Дерево пустое" << endl;
  79.             }
  80.             Postfiks(root);
  81.             _getch();
  82.             break;
  83.         case 8:
  84.             Solution(root, value, counter);
  85.             srdn = value / counter;
  86.             cout << "Среднее значение узлов равно ";
  87.             cout << srdn << endl;
  88.             result = root;
  89.             closestNode(root, srdn, result);
  90.             cout << "Ближайшая строка к среднему значению: ";
  91.             cout << "ФИО: " << result->FIO << ", " << "номер: " << result->number << endl;
  92.             _getch();
  93.             break;
  94.         case 9:
  95.             cout << "Программа завершена" << endl;
  96.             delete[] arr;
  97.             Clear(root);
  98.             break;
  99.         default:
  100.             cout << "Повторите еще раз" << endl;
  101.         }
  102.         system("cls");
  103.     }
  104. }
  105. void Add(Tree*& root, int num, char* fio)
  106. {
  107.     if (root == NULL)
  108.     {
  109.         root = new Tree;
  110.         root->number = num;
  111.         root->FIO = fio;
  112.         root->left = root->right = NULL;
  113.     }
  114.     if (num > root->number)
  115.     {
  116.         Add(root->right, num, fio);
  117.     }
  118.     else if (num < root->number)
  119.     {
  120.         Add(root->left, num, fio);
  121.     }
  122. }
  123.  
  124. void Prefiks(Tree*& node)
  125. {
  126.     if (node != NULL)
  127.     {
  128.         cout << "ФИО: " << node->FIO << ", " << "номер: " << node->number << endl;;
  129.         Prefiks(node->left);
  130.         Prefiks(node->right);
  131.     }
  132.  
  133. }
  134.  
  135. void Infiks(Tree*& node)
  136. {
  137.     if (node != NULL)
  138.     {
  139.         Infiks(node->left);
  140.         cout << "ФИО: " << node->FIO << ", " << "номер: " << node->number << endl;;
  141.         Infiks(node->right);
  142.     }
  143.  
  144. }
  145.  
  146. void Postfiks(Tree*& node)
  147. {
  148.     if (node != NULL)
  149.     {
  150.         Postfiks(node->left);
  151.         Postfiks(node->right);
  152.         cout << "ФИО: " << node->FIO << ", " << "номер: " << node->number << endl;
  153.     }
  154.  
  155. }
  156.  
  157. void SearchbyKey(Tree*& node)
  158. {
  159.     Tree* a = node;
  160.     int key;
  161.     bool search = false;
  162.     cout << "Введите ключ" << endl;
  163.     cin >> key;
  164.     while (a != NULL)
  165.     {
  166.         if (a->number > key)
  167.         {
  168.             a = a->right;
  169.         }
  170.         else if (a->number < key)
  171.         {
  172.             a = a->left;
  173.         }
  174.         else
  175.         {
  176.             search = true;
  177.             cout << "ФИО: " << a->FIO << ", " << "Номер:" << a->number << endl;
  178.             break;
  179.         }
  180.     }
  181.     if (!search)
  182.     {
  183.         cout << "Такого ключа нет" << endl;
  184.     }
  185. }
  186.  
  187. void Balance(Tree*& p, Tree** arr, int n, int k)
  188. {
  189.     if (n == k)
  190.     {
  191.         p = NULL;
  192.         return;
  193.     }
  194.     else
  195.     {
  196.         int m = (n + k) / 2;
  197.         p = arr[m];
  198.         Balance(p->left, arr, n, m);
  199.         Balance(p->right, arr, m + 1, k);
  200.     }
  201. }
  202.  
  203. void Clear(Tree*& p)
  204. {
  205.     if (p == NULL) return;
  206.     Clear(p->left);
  207.     Clear(p->right);
  208.     delete(p);
  209.     p = NULL;
  210. }
  211.  
  212. Tree* Delete(Tree* node, int inf)
  213. {
  214.     Tree* ps = node, * pr = node, * w = nullptr, * v = nullptr;
  215.     // Поиск удаляемого узла  
  216.     while ((ps != NULL) && (ps->number != inf))
  217.     {
  218.         pr = ps;
  219.         if (inf < ps->number)
  220.         {
  221.             ps = ps->left;
  222.         }
  223.         else
  224.         {
  225.             ps = ps->right;
  226.         }
  227.     }
  228.     if (ps == NULL)
  229.     {
  230.         return node; // Если узел не найден
  231.     }
  232.  
  233.     if ((ps->left == NULL) && (ps->right == NULL)) // Если узел не имеет дочерей
  234.     {
  235.         if (ps == pr) // Если это был последний элемент  
  236.         {
  237.             delete(ps);
  238.             return NULL;
  239.         }
  240.  
  241.         if (pr->left == ps) // Если удаляемый узел слева  
  242.         {
  243.             pr->left = NULL;
  244.         }
  245.  
  246.         else               // Если удаляемый узел справа      
  247.         {
  248.             pr->right = NULL;
  249.         }
  250.  
  251.         delete(ps);
  252.         return node;
  253.     }
  254.  
  255.     if (ps->left == NULL) // Если узел имеет дочь только справа  
  256.     {
  257.         if (ps == pr)// Если удаляется корень
  258.         {
  259.             ps = ps->right;
  260.             delete(pr);
  261.             return ps;
  262.         }
  263.  
  264.         if (pr->left == ps) // Если удаляемый узел слева  
  265.         {
  266.             pr->left = ps->right;
  267.         }
  268.  
  269.         else    // Если удаляемый узел справа
  270.         {
  271.             pr->right = ps->right;
  272.         }
  273.  
  274.         delete(ps);
  275.         return node;
  276.     }
  277.  
  278.     // Если узел имеет дочь только слева  
  279.     if (ps->right == NULL)
  280.     {
  281.         if (ps == pr) // Если удаляется корень  
  282.         {
  283.             ps = ps->left;
  284.             delete(pr);
  285.             return ps;
  286.         }
  287.  
  288.         if (pr->left == ps) // Если удаляемый узел слева  
  289.             pr->left = ps->left;
  290.         else    // Если удаляемый узел справа    
  291.             pr->right = ps->left;
  292.         delete(ps);
  293.         return node;
  294.     }
  295.  
  296.     // Если узел имеет двух дочерей
  297.     w = ps->left;
  298.     if (w->right == NULL) // Если максимальный следует за ps
  299.     {
  300.         w->right = ps->right;
  301.     }
  302.  
  303.     else   // Если максимальный не следует за ps
  304.     {
  305.         while (w->right != NULL)
  306.         {
  307.             v = w;
  308.             w = w->right;
  309.         }
  310.         v->right = w->left;
  311.         w->left = ps->left;
  312.         w->right = ps->right;
  313.     }
  314.  
  315.     if (ps == pr) // Если удаляется корень  
  316.     {
  317.         delete(ps);
  318.         return w;
  319.     }
  320.  
  321.     if (pr->left == ps) // Если удаляемый узел слева  
  322.     {
  323.         pr->left = w;
  324.     }
  325.  
  326.     else    // Если удаляемый узел справа  
  327.     {
  328.         pr->right = w;
  329.     }
  330.     delete(ps);
  331.     return node;
  332. }
  333.  
  334. void Solution(Tree* r, int& value, int& counter)
  335. {
  336.     if (r)
  337.     {
  338.         value += r->number;
  339.         ++counter;
  340.         Solution(r->left, value, counter);
  341.         Solution(r->right, value, counter);
  342.     }
  343. }
  344.  
  345. void closestNode(Tree*& root, int sredn, Tree*& result)
  346. {
  347.     if (root == NULL)
  348.     {
  349.         return;
  350.     }
  351.     if (abs(root->number - sredn) < abs(result->number - sredn))
  352.     {
  353.         result = root;
  354.     }
  355.     if (sredn < root->number)
  356.     {
  357.         closestNode(root->left, sredn, result);
  358.     }
  359.     else
  360.     {
  361.         closestNode(root->right, sredn, result);
  362.     }
  363.  
  364. }
RAW Paste Data