Advertisement
baadgeorge

siaod_lr2

Apr 23rd, 2021
74
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 7.50 KB | None | 0 0
  1. #include <iostream>
  2. #include <Windows.h>
  3. #include <ctime>
  4. #include <iomanip>
  5.  
  6. #define char_A 'А'
  7. #define char_R 'Я'
  8. #define char_a 'а'
  9. #define char_r 'я'
  10.  
  11. int maximum(int a, int b)
  12. {
  13.     if (a > b) return a;
  14.     else return b;
  15. }
  16.  
  17. int minimum(int a, int b)
  18. {
  19.     if (a > b) return b;
  20.     else return a;
  21. }
  22.  
  23. struct NODE
  24. {
  25.     char key;
  26.     NODE* left;
  27.     NODE* right;
  28. };
  29.  
  30. typedef NODE* NODEPTR;
  31.  
  32. NODEPTR initTree(char _key)
  33. {
  34.     NODEPTR newNODEPTR = new NODE;  // Создание нового узла
  35.     newNODEPTR->key = _key;
  36.     newNODEPTR->left = NULL;
  37.     newNODEPTR->right = NULL;
  38.     return newNODEPTR;
  39. }
  40.  
  41. // Поиск с включением
  42. NODEPTR searchInsert(NODEPTR Root, char _key)
  43. {
  44.     NODEPTR tmp = Root;
  45.     NODEPTR prev = NULL;
  46.     bool found = false;
  47.  
  48.     while ((tmp != NULL) && (found == false))
  49.     {
  50.         prev = tmp; // запоминаем предыдущий
  51.         if (_key == tmp->key)
  52.             found = true;
  53.         else
  54.         {
  55.             if (_key < tmp->key) tmp = tmp->left;
  56.             else  tmp = tmp->right;
  57.         }
  58.     }
  59.     if (found)
  60.         return tmp; // в дереве уже есть такой ключ
  61.  
  62.     NODEPTR newNODEPTR = new NODE;  // Создание нового узла
  63.     newNODEPTR->key = _key;
  64.     newNODEPTR->left = NULL;
  65.     newNODEPTR->right = NULL;
  66.     if (_key < prev->key)
  67.         // Присоединение к левому  поддереву предка
  68.         prev->left = newNODEPTR;
  69.     else
  70.         // Присоединение к правому поддереву предка
  71.         prev->right = newNODEPTR;
  72.     return newNODEPTR;
  73. }
  74.  
  75. int getNodeCount(NODEPTR Root)
  76. {
  77.     if (Root == NULL) return 0;
  78.     else return getNodeCount(Root->left) + getNodeCount(Root->right) + 1;
  79. }
  80.  
  81. bool isVowel(char _key)
  82. {
  83.     char mas[18] = { 'А', 'а', 'У', 'у', 'О', 'о', 'Ы', 'ы', 'И', 'и', 'Э', 'э', 'Я', 'я', 'Ю', 'ю', 'К', 'е' };
  84.     for (int i = 0; i < 18; i++)
  85.     {
  86.         if (_key == mas[i]) return true;
  87.     }
  88.     return false;
  89. }
  90.  
  91. int getVowelCount(NODEPTR Root, int level)
  92. {
  93.     int tmp = 0;
  94.     if (Root == NULL) return 0;
  95.     if ((level % 2 == 0) && (isVowel(Root->key) == true)) tmp = 1;
  96.     return getVowelCount(Root->left, level + 1) + getVowelCount(Root->right, level + 1) + tmp;
  97. }
  98.  
  99. int getMaxTreeHeight(NODEPTR Root) {
  100.     if (Root == NULL)
  101.         return 0;
  102.     return 1 + maximum(getMaxTreeHeight(Root->left), getMaxTreeHeight(Root->right));
  103. }
  104.  
  105. int getMinTreeHeight(NODEPTR Root) {
  106.     if (Root == NULL)
  107.         return 0;
  108.     return 1 + minimum(getMinTreeHeight(Root->left), getMinTreeHeight(Root->right));
  109. }
  110.  
  111. void printTree(NODEPTR Root, int level)
  112. {
  113.     if (Root != NULL)
  114.     {
  115.         printTree(Root->right, level + 1); // вывод левого поддерева
  116.         for (int i = 0; i < level; i++) std::cout << "   ";
  117.         std::cout << Root->key << std::endl; // вывод корня поддерева
  118.         printTree(Root->left, level + 1); // вывод правого поддерева
  119.     }
  120. }
  121.  
  122. void traverseSymmetricTree(NODEPTR Root)
  123. {
  124.     if (Root == NULL) return;
  125.     else
  126.     {
  127.         traverseSymmetricTree(Root->left);
  128.         std::cout << Root->key << " ";
  129.         traverseSymmetricTree(Root->right);
  130.     }
  131. }
  132.  
  133. void deleteTree(NODEPTR* Root)
  134. {
  135.     NODEPTR tmp = *Root;
  136.     if (*Root == NULL) return;
  137.  
  138.     deleteTree(&(tmp)->left);
  139.     deleteTree(&(tmp)->right);
  140.     delete *Root;
  141.     *Root = NULL;
  142.     return;
  143. }
  144.  
  145. int deleteNode(NODEPTR* Root, char _key)
  146. {
  147.     NODEPTR tmp = *Root;
  148.     NODEPTR prev = NULL;
  149.     bool found = false;
  150.     bool isLeftChild = false;
  151.  
  152.     // поиск узла
  153.     while ((tmp != NULL) && (found == false))
  154.     {
  155.         if (_key == tmp->key)
  156.         {
  157.             // найден искомый узел
  158.             found = true;
  159.             break;
  160.         }
  161.         prev = tmp; // запоминаем предыдущий
  162.         if (_key < tmp->key)
  163.         {
  164.             // ищем искомый узел в левом поддереве
  165.             tmp = tmp->left;
  166.             isLeftChild = true;
  167.         }
  168.         else
  169.         {
  170.             // ищем искомый узел в правом поддереве
  171.             tmp = tmp->right;
  172.             isLeftChild = false;
  173.         }
  174.     }
  175.     // если узел не найден - выход из функции
  176.     if (found == false) return -1;
  177.  
  178.     // анализируем число потомков найденного узла
  179.     if ((tmp->left == NULL) && (tmp->right == NULL))
  180.     {
  181.         deleteTree(&tmp);
  182.         if (prev == NULL)
  183.         {
  184.             *Root = NULL;
  185.             return 0;
  186.         }
  187.         if (isLeftChild == true) prev->left = NULL;
  188.         else prev->right = NULL;
  189.         return 0;
  190.     }
  191.  
  192.     if ((tmp->left != NULL) && (tmp->right != NULL))
  193.     {
  194.         NODEPTR foundNode = tmp;
  195.         tmp = tmp->right;
  196.         while (tmp->left != NULL)
  197.         {
  198.             tmp = tmp->left;
  199.         }
  200.         tmp->left = foundNode->left;
  201.         if (prev == NULL)
  202.         {
  203.             *Root = foundNode->right;
  204.             delete foundNode;
  205.             return 0;
  206.         }
  207.         if (isLeftChild == true) prev->left = foundNode->right;
  208.         else prev->right = foundNode->right;
  209.         delete foundNode;
  210.         return 0;
  211.     }
  212.  
  213.     if (tmp->left != NULL)
  214.     {
  215.         if (prev == NULL)
  216.         {
  217.             *Root = tmp->left;
  218.             delete tmp;
  219.             return 0;
  220.         }
  221.         if (isLeftChild == true) prev->left = tmp->left;
  222.         else prev->right = tmp->left;
  223.         return 0;
  224.     }
  225.  
  226.     if (tmp->right != NULL)
  227.     {
  228.         if (prev == NULL)
  229.         {
  230.             *Root = tmp->right;
  231.             delete tmp;
  232.             return 0;
  233.         }
  234.         if (isLeftChild == true) prev->left = tmp->right;
  235.         else prev->right = tmp->right;
  236.         return 0;
  237.     }
  238.  
  239.     return 0;
  240. }
  241.  
  242. struct DATA
  243. {
  244.     char* mas;
  245.     int size;
  246. };
  247.  
  248. typedef struct DATA Data;
  249.  
  250. // ФУНКЦИЯ НАХОЖДЕНИЯ СЛУЧАЙНОГО ЧИСЛА
  251. char random(int N)
  252. {
  253.     int result = rand() % N;
  254.     return (char)result;
  255. }
  256.  
  257. // ФУНКЦИЯ ФОРМИРОВАНИЯ СЛУЧАЙНОГО МАССИВА ДАННЫХ
  258. int formRandCharArray(Data* data)
  259. {
  260.     char tmp = NULL;
  261.     int i = 0;
  262.  
  263.     while (i < data->size)
  264.     {
  265.         int coin = random(2);
  266.         if (coin == 0)
  267.         {
  268.             tmp = char_A + random(char_R - char_A + 1);
  269.         }
  270.         else
  271.         {
  272.             tmp = char_a + random(char_r - char_a + 1);
  273.         }
  274.         data->mas[i] = tmp;
  275.         i++;
  276.     }
  277.     return 0;
  278. }
  279.  
  280. // ФУНКЦИЯ ВЫВОДА МАССИВА НА ЭКРАН
  281. void printMas(Data& data)
  282. {
  283.     for (int i = 0; i < data.size; i++)
  284.         std::cout << data.mas[i] << ' ';
  285.     std::cout << '\n';
  286. }
  287.  
  288. int main()
  289. {
  290.     system("color F0");
  291.     setlocale(LC_ALL, "RUS");
  292.  
  293.     srand(time(NULL));
  294.  
  295.     NODEPTR Tree = NULL;
  296.  
  297.     Data Array{ NULL, 18 };
  298.  
  299.     Array.mas = new char[Array.size];
  300.  
  301.     formRandCharArray(&Array);
  302.  
  303.     std::cout << "Массив случайных букв русского языка: "; printMas(Array);
  304.  
  305.     Tree = initTree(Array.mas[0]);
  306.  
  307.     for (int i = 1; i < Array.size; i++)
  308.     {
  309.         searchInsert(Tree, Array.mas[i]);
  310.     }
  311.  
  312.     std::cout << "\n*****************************************************\n";
  313.     std::cout << "\nРезультирующее бинарное дерево поиска: \n\n";
  314.     printTree(Tree, 0);
  315.     std::cout << "\nМаксимальная высота: " << getMaxTreeHeight(Tree) << ", Минимальная высота: " << getMinTreeHeight(Tree) << ", Число узлов: " << getNodeCount(Tree) << ", Число гласных букв (на четных уровнях): " << getVowelCount(Tree,1) << "\n";
  316.  
  317.     std::cout << "\nСимметричный обход дерева: ";
  318.     traverseSymmetricTree(Tree);
  319.     std::cout << "\n";
  320.  
  321.     char tmp = Array.mas[random(Array.size)];
  322.     //char tmp = Array.mas[0];
  323.     std::cout << "\nУдаление узла '" << tmp << "' из дерева\n";
  324.     deleteNode(&Tree, tmp);
  325.  
  326.     std::cout << "\nИзмененное бинарное дерево поиска: \n\n";
  327.     printTree(Tree, 0);
  328.  
  329.     std::cout << "\n\n*****************************************************\n";
  330.  
  331.     deleteTree(&Tree);
  332.  
  333.     delete[] Array.mas;
  334. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement