Eugene0091

Laba_5 SIAOD

Oct 31st, 2020
1,018
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include "BinaryTree.h"
  2. #include <iostream>
  3. #include <fstream>
  4.  
  5.  
  6. const std::string FILE_ERROR = "File is not found. Check the existence of the file and the entered pass. Try again.";
  7.  
  8. void fillTree(BinaryTree& tree);
  9. char chooseSelection(char firstSelection, char secondSelection);
  10. void fillTreeFile(BinaryTree& tree);
  11. void fillTreeKeyboard(BinaryTree& tree);
  12. void checkOnTreeSize(BinaryTree tree);
  13. std::string inputPath();
  14. int checkInputNumber(int min, int max);
  15.  
  16. int choiceElementFromDelete()
  17. {
  18.     const int MIN_INT = -214748364;
  19.     const int MAX_INT = 214748364;
  20.     std::cout << "Enter element for delete:\n";
  21.     return checkInputNumber(MIN_INT, MAX_INT);
  22. }
  23.  
  24. int checkInputNumber(int min, int max)
  25. {
  26.     int num = 0;
  27.     std::string s = "";
  28.     bool isCorrect = true;
  29.     do {
  30.         std::cin >> s;
  31.         try
  32.         {
  33.  
  34.             num = std::stoi(s);
  35.         }
  36.         catch (std::invalid_argument const& e)
  37.         {
  38.             std::cout << "Bad input: std::invalid_argument thrown" << '\n';
  39.         }
  40.         catch (std::out_of_range const& e)
  41.         {
  42.             std::cout << "Integer overflow: std::out_of_range thrown" << '\n';
  43.         }
  44.         if ((num > min - 1) && (num < max + 1))
  45.         {
  46.             isCorrect = false;
  47.         }
  48.         else
  49.         {
  50.             std::cout << "Error!Enter a number:\n";
  51.         }
  52.     } while (isCorrect);
  53.     return num;
  54. }
  55.  
  56.  
  57. void fillTree(BinaryTree& tree)
  58. {
  59.     const std::string FILL_LIST_MESSAGE = "Fill your tree. Choose the selection of your input(F - File input, K - Keyboard input). ";
  60.     std::cout << (FILL_LIST_MESSAGE) << std::endl;
  61.     if (chooseSelection('F', 'K') == 'F')
  62.     {
  63.         fillTreeFile(tree);
  64.     }
  65.     else
  66.     {
  67.         fillTreeKeyboard(tree);
  68.     }
  69.     checkOnTreeSize(tree);
  70. }
  71.  
  72. char chooseSelection(char firstSelection, char secondSelection)
  73. {
  74.     const std::string ANSWER_MISTAKE_MESSAGE = "Incorrect answer. Please, try again.\n";
  75.     std::string strAnswer;
  76.     char answer;
  77.     bool isNotCorrect;
  78.     do
  79.     {
  80.         isNotCorrect = false;
  81.         std::cout << "Your selection: ";
  82.         std::cin >> strAnswer;
  83.         answer = toupper(strAnswer[0]);
  84.         if ((strAnswer.size() > 1) || (answer != firstSelection && answer != secondSelection))
  85.         {
  86.             std::cout << ANSWER_MISTAKE_MESSAGE;
  87.             isNotCorrect = true;
  88.         }
  89.     } while (isNotCorrect);
  90.     return answer;
  91. }
  92.  
  93. void fillTreeFile(BinaryTree& tree)
  94. {
  95.     const std::string FILE_VAR_MESSAGE = "Incorrect tree in the file. You need to write in the file tree with numbers and separated by spaces\n";
  96.     bool isNotCorrect;
  97.     std::string tempInput;
  98.     int temp;
  99.     do
  100.     {
  101.         isNotCorrect = false;
  102.         std::ifstream userFile(inputPath());
  103.         if (userFile)
  104.         {
  105.             try
  106.             {
  107.                 while (!userFile.eof())
  108.                 {
  109.                     userFile >> tempInput;
  110.                     tree.add(std::stoi(tempInput));
  111.                 }
  112.             }
  113.             catch (std::invalid_argument const& e)
  114.             {
  115.                 std::cout << FILE_VAR_MESSAGE;
  116.                 isNotCorrect = true;
  117.             }
  118.         }
  119.         else
  120.         {
  121.             std::cout << FILE_ERROR << std::endl;
  122.             isNotCorrect = true;
  123.         }
  124.     } while (isNotCorrect);
  125.  
  126. }
  127.  
  128. void fillTreeKeyboard(BinaryTree& tree)
  129. {
  130.     const std::string FILL_LIST_KEYBOARD = "Fill your list by keyboard. When you want to stop enter 'STOP'\n";
  131.     const std::string VAR_MISTAKE_MESSAGE = "Error. Your input should be a number. Please, try again.\n";
  132.     const std::string STOP_WORD = "STOP";
  133.     bool isContinue = true;
  134.     std::string tempInput;
  135.     std::cout << FILL_LIST_KEYBOARD;
  136.     do
  137.     {
  138.         std::cout << "Enter " << (tree.size + 1) << " element of the list: ";
  139.         std::cin >> tempInput;
  140.         if (tempInput == STOP_WORD)
  141.         {
  142.             isContinue = false;
  143.         }
  144.         else
  145.         {
  146.             try
  147.             {
  148.                 tree.add(std::stoi(tempInput));
  149.             }
  150.             catch (std::invalid_argument const& e)
  151.             {
  152.                 std::cout << VAR_MISTAKE_MESSAGE;
  153.             }
  154.         }
  155.     } while (isContinue);
  156. }
  157.  
  158. void checkOnTreeSize(BinaryTree tree)
  159. {
  160.     if (tree.size == 0)
  161.     {
  162.         const std::string EMPTY_LIST_MESSAGE = "Your list is empty. Do you want to fill it again? (Y - Yes, N - No)\n";
  163.         std::cout << EMPTY_LIST_MESSAGE;
  164.         if (chooseSelection('N', 'Y') == 'Y')
  165.         {
  166.             fillTree(tree);
  167.         }
  168.     }
  169. }
  170.  
  171. std::string inputPath()
  172. {
  173.     const std::string INPUT_PATH_EXAMPLE = "Please, input the path to the file. For example: C:/Users/lenovo/text.txt.\nYour path: ";
  174.     std::string filePath;
  175.     std::cout << INPUT_PATH_EXAMPLE;
  176.     std::cin >> filePath;
  177.     return filePath;
  178. }
  179.  
  180. void menu(BinaryTree tree)
  181. {
  182.     std::cout << "\n********************************************"
  183.                  "\n1. Delete element.\n"
  184.                  "2. Find element.\n"
  185.                  "3. Tree walk (direct, symmentrical, reverse).\n"
  186.                  "4. Add element.\n"
  187.                  "5. Watch Tree.\n"
  188.                  "6. Exit.\n"
  189.                  "********************************************"
  190.                  "\nYour choice: "<< std::endl;
  191.     int choice = checkInputNumber(1, 6);
  192.     switch (choice)
  193.     {
  194.     case 1:
  195.         //tree.root = tree.deletion(tree.root, choiceElementFromDelete());
  196.         tree.deleteNode(tree.root, choiceElementFromDelete());
  197.         std::cout << "RESULT:\n";
  198.         std::cout << tree.takeTreeVisual(tree.root) << std::endl;
  199.         menu(tree);
  200.         break;
  201.     case 2:
  202.         tree.findElement(tree.root, choiceElementFromDelete());
  203.         menu(tree);
  204.         break;
  205.     case 3:
  206.         std::cout << "\nWalk direct: \n";
  207.         tree.directWalk(tree.root);
  208.         std::cout << "\nWalk symmetrical: \n";
  209.         tree.symmetricalWalk(tree.root);
  210.         std::cout << "\nWalk reverse: \n";
  211.         tree.reverseWalk(tree.root);
  212.         menu(tree);
  213.         break;
  214.     case 4:
  215.         fillTreeKeyboard(tree);
  216.         menu(tree);
  217.         break;
  218.     case 5:
  219.         std::cout << "Main Tree: \n";
  220.         std::cout << tree.takeTreeVisual(tree.root) << std::endl;
  221.         menu(tree);
  222.         break;
  223.     case 6:
  224.         std::cout << "Program completed.";
  225.         exit(0);
  226.     }
  227. }
  228.  
  229. int main()
  230. {
  231.     const std::string PROGRAM_DESCRIPTION = "The trees. This program deletes an element from a given binary tree.";
  232.     const std::string MAIN_TREE = "Your main tree: ";
  233.     BinaryTree tree;
  234.     std::cout << PROGRAM_DESCRIPTION << std::endl;
  235.     fillTree(tree);
  236.     std::cout << MAIN_TREE << std::endl;
  237.     std::cout << tree.takeTreeVisual(tree.root) << std::endl;
  238.     menu(tree);
  239.     return 0;
  240. }
  241.  
  242.  
  243.  
  244.  
  245.  
  246.  
  247. #pragma once
  248. #include<sstream>
  249. #include <iostream>
  250. #include <queue>
  251. #include <queue>
  252.  
  253. struct Node
  254. {
  255.     int value;
  256.     Node* left;
  257.     Node* right;
  258. };
  259.  
  260. struct BinaryTree
  261. {
  262.     Node* root = nullptr;
  263.     int size = 0;
  264.  
  265.     void directWalk(Node*& root)
  266.     {
  267.         if (root != nullptr)
  268.         {
  269.             std::cout << root->value << " ";
  270.             directWalk(root->left);
  271.             directWalk(root->right);
  272.         }
  273.     }
  274.  
  275.     void symmetricalWalk(Node*& root)
  276.     {
  277.         if (root != nullptr)
  278.         {
  279.             symmetricalWalk(root->left);
  280.             std::cout << root->value << " ";
  281.             symmetricalWalk(root->right);
  282.         }
  283.     }
  284.  
  285.     void reverseWalk(Node*& root)
  286.     {
  287.         if (root != nullptr)
  288.         {
  289.             reverseWalk(root->left);
  290.             reverseWalk(root->right);
  291.             std::cout << root->value << " ";
  292.         }
  293.     }
  294.  
  295.     void findElement(Node*& root, int key)
  296.     {
  297.         Node* node;
  298.         if (root == nullptr)
  299.         {
  300.             std::cout << "Binary tree is empty!\n";
  301.             return;
  302.         }
  303.         while (root != nullptr)
  304.         {
  305.             if (root->value == key)
  306.             {
  307.                 std::cout << "\nElement " << root->value << " is found!\n";
  308.                 return;
  309.             }
  310.             if (root->value < key)
  311.             {
  312.                 root = root->right;
  313.             }
  314.             else
  315.             {
  316.                 root = root->left;
  317.             }
  318.         }
  319.         std::cout << "\nElement " << key << " not is found!\n";
  320.     }
  321.  
  322.     Node* maximumKey(Node* ptr)
  323.     {
  324.         while (ptr->right != nullptr)
  325.         {
  326.             ptr = ptr->right;
  327.         }
  328.         return ptr;
  329.     }
  330.  
  331.     void deleteNode(Node*& root, int key)
  332.     {
  333.         if (root == nullptr)
  334.         {
  335.             std::cout << "Binary tree is empty!\n";
  336.             return;
  337.         }
  338.         if (key < root->value)
  339.             deleteNode(root->left, key);
  340.         else if (key > root->value)
  341.             deleteNode(root->right, key);
  342.         else
  343.         {
  344.             if (root->left == nullptr && root->right == nullptr)
  345.             {
  346.                 delete root;
  347.                 root = nullptr;
  348.             }
  349.             else if (root->left && root->right)
  350.             {
  351.                 Node* predecessor = maximumKey(root->left);
  352.                 root->value = predecessor->value;
  353.                 deleteNode(root->left, predecessor->value);
  354.             }
  355.             else
  356.             {
  357.                 Node* child = (root->left) ? root->left : root->right;
  358.                 Node* curr = root;
  359.                 root = child;
  360.                 delete curr;
  361.             }
  362.         }
  363.     }
  364.  
  365.     /* function to delete the given deepest node
  366. (d_node) in binary tree */
  367.     void deletDeepest(struct Node* root,
  368.         struct Node* d_node)
  369.     {
  370.         std::queue<struct Node*> q;
  371.         q.push(root);
  372.  
  373.         // Do level order traversal until last node
  374.         struct Node* temp;
  375.         while (!q.empty()) {
  376.             temp = q.front();
  377.             q.pop();
  378.             if (temp == d_node) {
  379.                 temp = NULL;
  380.                 delete (d_node);
  381.                 return;
  382.             }
  383.             if (temp->right) {
  384.                 if (temp->right == d_node) {
  385.                     temp->right = NULL;
  386.                     delete (d_node);
  387.                     return;
  388.                 }
  389.                 else
  390.                     q.push(temp->right);
  391.             }
  392.  
  393.             if (temp->left) {
  394.                 if (temp->left == d_node) {
  395.                     temp->left = NULL;
  396.                     delete (d_node);
  397.                     return;
  398.                 }
  399.                 else
  400.                     q.push(temp->left);
  401.             }
  402.         }
  403.     }
  404.  
  405.     /* function to delete element in binary tree */
  406.     Node* deletion(struct Node* root, int key)
  407.     {
  408.         if (root == NULL)
  409.             return NULL;
  410.  
  411.         if (root->left == NULL && root->right == NULL) {
  412.             if (root->value == key)
  413.                 return NULL;
  414.             else
  415.                 return root;
  416.         }
  417.  
  418.         std::queue<struct Node*> q;
  419.         q.push(root);
  420.  
  421.         struct Node* temp;
  422.         struct Node* key_node = NULL;
  423.  
  424.         // Do level order traversal to find deepest
  425.         // node(temp) and node to be deleted (key_node)
  426.         while (!q.empty()) {
  427.             temp = q.front();
  428.             q.pop();
  429.  
  430.             if (temp->value == key)
  431.                 key_node = temp;
  432.  
  433.             if (temp->left)
  434.                 q.push(temp->left);
  435.  
  436.             if (temp->right)
  437.                 q.push(temp->right);
  438.         }
  439.  
  440.         if (key_node != NULL) {
  441.             int x = temp->value;
  442.             deletDeepest(root, temp);
  443.             key_node->value = x;
  444.         }
  445.         return root;
  446.     }
  447.  
  448.     void add_node(int value, Node*& Tree)
  449.     {
  450.         if (Tree == NULL)
  451.         {
  452.             Tree = new Node;
  453.             Tree->value = value;
  454.             Tree->left = NULL;
  455.             Tree->right = NULL;
  456.         }
  457.         else
  458.         {
  459.             if (value == Tree->value)
  460.             {
  461.                 std::cout << "This element is already in Tree: " << Tree->value << std::endl;
  462.                 --size;
  463.                 return;
  464.             }
  465.             if (value < Tree->value)
  466.             {
  467.                 add_node(value, Tree->left);
  468.             }
  469.             else
  470.             {
  471.                 add_node(value, Tree->right);
  472.             }
  473.         }
  474.     }
  475.  
  476.     void add(int value) {
  477.  
  478.         add_node(value, root);
  479.         size++;
  480.     }
  481.  
  482.     std::string takeTreeVisual(Node* rootNode)
  483.     {
  484.         const std::string EMPTY_TREE = "Your tree is empty. Sorry.";
  485.         if (size == 0)
  486.         {
  487.             return EMPTY_TREE;
  488.         }
  489.         return processPreOrder(rootNode);
  490.     }
  491.  
  492.     std::string processPreOrder(Node* root)
  493.     {
  494.         std::stringstream treeStream;
  495.         if (root == nullptr)
  496.         {
  497.             return "";
  498.         }
  499.         treeStream << "";
  500.         treeStream << root->value;
  501.         std::string pointerLeft;
  502.         if (root->right != nullptr)
  503.         {
  504.             pointerLeft = "|--";
  505.         }
  506.         else {
  507.             pointerLeft = "`--";
  508.         }
  509.         processNodes(treeStream, "", pointerLeft, root->left, root->right != nullptr);
  510.         processNodes(treeStream, "", "`--", root->right, false);
  511.         std::string tree = treeStream.str();
  512.         return tree;
  513.     }
  514.  
  515.     void processNodes(std::stringstream& tree, std::string padding, std::string pointer,
  516.         Node* node, bool hasRightNode)
  517.     {
  518.         if (node != nullptr)
  519.         {
  520.             tree << "\n";
  521.             tree << padding;
  522.             tree << pointer;
  523.             if (node->value < 0)
  524.             {
  525.                 tree << "(" << node->value << ")";
  526.             }
  527.             else
  528.             {
  529.                 tree << node->value;
  530.             }
  531.             if (hasRightNode)
  532.             {
  533.                 padding += "|  ";
  534.             }
  535.             else
  536.             {
  537.                 padding += "   ";
  538.             }
  539.             if (node->right != nullptr)
  540.             {
  541.                 pointer = "|--";
  542.             }
  543.             else
  544.             {
  545.                 pointer = "`--";
  546.             }
  547.             processNodes(tree, padding, pointer, node->left, node->right != nullptr);
  548.             processNodes(tree, padding, "|--", node->right, false);
  549.         }
  550.     }
  551. };
  552.  
RAW Paste Data