Advertisement
baadgeorge

Untitled

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