HabKaffee

Binary Tree

Oct 31st, 2020
137
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <fstream>
  3. #include <algorithm>
  4. #include <string>
  5.  
  6. std::ifstream FileIn("Task.txt");
  7.  
  8. int check = -1;
  9.  
  10. struct Tree {
  11.     int value;
  12.     Tree* left;
  13.     Tree* right;
  14. };
  15.  
  16.  
  17.  
  18.  
  19. void addToTree(Tree **root, int value) {
  20.     if ((*root) == NULL) {
  21.         (*root) = new Tree;
  22.         (*root)->value = value;
  23.         (*root)->left = NULL;
  24.         (*root)->right = NULL;
  25.     }
  26.     else if (value <= (*root)->value) {
  27.         addToTree(&(*root)->left, value);
  28.     }
  29.     else {
  30.         addToTree(&(*root)->right, value);
  31.     }
  32. }
  33.  
  34. void fillTree(Tree** root) {
  35.     int val;
  36.     while (1) {
  37.         FileIn >> val;
  38.         if (FileIn.eof()) {
  39.             break;
  40.         }
  41.         addToTree(&(*root), val);
  42.     }
  43. }
  44.  
  45.  
  46. void sortPrint(Tree** root, int level){
  47.     if (*root != NULL){
  48.         sortPrint(&((**root).right), level + 1);
  49.         for (int i = 1; i <= level; i++) {
  50.             std::cout << "\t";
  51.         }
  52.         std::cout << (**root).value << std::endl;
  53.         sortPrint(&((**root).left), level + 1);
  54.     }
  55. }
  56.  
  57.  
  58. Tree* Search(Tree* root, int value) {
  59.     if (root == NULL) {
  60.         return NULL;
  61.     }
  62.     if (root->value == value) {
  63.         check = 1;
  64.         return root;
  65.     }
  66.     if (value < root->value) {
  67.         return Search(root->left, value);
  68.     }
  69.     else {
  70.         return Search(root->right, value);
  71.     }
  72. }
  73.  
  74. void deleteTree(Tree* root) {
  75.     if (root != NULL) {
  76.         deleteTree(root->left);
  77.         deleteTree(root->right);
  78.         delete root;
  79.     }
  80. }
  81.  
  82. Tree* searchInInterval(Tree* root, int a, int b) {
  83.     if (root == NULL) {
  84.         return NULL;
  85.     }
  86.  
  87.     if (root->value >= b) {
  88.         searchInInterval(root->left, a, b);
  89.     }
  90.     if (root->value <= a) {
  91.         searchInInterval(root->right, a, b);
  92.     }
  93.  
  94.  
  95.     if (root->value > a && root->value < b) {
  96.         //if (root->value != a && root->value != b) {
  97.             std::cout << root->value << "  ";
  98.         //}
  99.         searchInInterval(root->left, a, b);
  100.         searchInInterval(root->right, a, b);
  101.     }
  102. }
  103.  
  104. void menu(int variant, Tree *root, int value, int a, int b) {
  105.     std::cout << "please, select the option\n" << "1. Print the tree\n2. Add value to tree\n3. Search for value in tree\n4. Search for values in interval (a,b)\n5. Exit" << std::endl;
  106.     while (variant != 5) {
  107.         std::cin >> variant;
  108.         switch (variant) {
  109.         case 1:
  110.             std::cout << "===============================================\n";
  111.             sortPrint(&root, 0);
  112.             std::cout << "===============================================\n";
  113.             break;
  114.         case 2:
  115.             std::cout << "===============================================\n";
  116.             std::cout << "Enter value to add\n";
  117.             std::cin >> value;
  118.             addToTree(&root, value);
  119.             std::cout << "Add is successful\n";
  120.             value = 0;
  121.             std::cout << "===============================================\n";
  122.             break;
  123.         case 3:
  124.             std::cout << "===============================================\n";
  125.             std::cout << "Enter value to find\n";
  126.             std::cin >> value;
  127.             Search(root, value);
  128.             if (check == -1) {
  129.                 std::cout << "Element with this value doesn't exist in the tree\n";
  130.             }
  131.             else if (check == 1) {
  132.                 std::cout << "Element with this value exist in the tree\n";
  133.             }
  134.             check = -1;
  135.             std::cout << "===============================================\n";
  136.             break;
  137.         case 4:
  138.             std::cout << "===============================================\n";
  139.             std::cout << "Write down borders of interval\n";
  140.             std::cin >> a>> b;
  141.             if (a > b) {
  142.                 std::swap(a, b);
  143.             }
  144.             std::cout << "a = " << a << " b = " << b << std::endl;
  145.             searchInInterval(root, a, b);
  146.             std::cout << std::endl;
  147.             std::cout << "===============================================\n";
  148.             break;
  149.         case 5:
  150.             std::cout << "===============================================\n";
  151.             std::cout << "Have a nice day :)\n";
  152.             break;
  153.  
  154.         default:
  155.             std::cout << "===============================================\n";
  156.             std::cout << "Wrong command, try again\n";
  157.             break;
  158.         }
  159.     }
  160. }
  161.  
  162.  
  163. int main() {
  164.     Tree* root = NULL;
  165.     fillTree(&root);
  166.     int value =  0, variant =  0, a =0, b = 0;
  167.     menu(variant, root, value,a,b);
  168.     deleteTree(root);
  169.     return 0;
  170. }
RAW Paste Data Copied