The text below is selected, press Ctrl+C to copy to your clipboard. (⌘+C on Mac) No line numbers will be copied.
Guest
Tree insertion nd delete
By Guest on 8th December 2023 08:52:16 AM | Syntax: PYTHON | Views: 89


New Paste New paste | Download Paste Download | Toggle Line Numbers Show/Hide line no. | Copy Paste Copy text to clipboard
  1. #include<iostream>
  2. #define SPACE 10
  3. using namespace std;
  4. class TreeNode {
  5.   public:
  6.     int value;
  7.   TreeNode * left;
  8.   TreeNode * right;
  9.   TreeNode() {
  10.     value = 0;
  11.     left = NULL;
  12.     right = NULL;
  13.   }
  14.   TreeNode(int v) {
  15.     value = v;
  16.     left = NULL;
  17.     right = NULL;
  18.   }
  19. };
  20.  
  21. class BST {
  22.   public:
  23.     TreeNode * root;
  24.   BST() {
  25.     root = NULL;
  26.   }
  27.   bool isTreeEmpty() {
  28.     if (root == NULL) {
  29.       return true;
  30.     } else {
  31.       return false;
  32.     }
  33.   }
  34.  
  35.   void insertNode(TreeNode * new_node) {
  36.     if (root == NULL) {
  37.       root = new_node;
  38.       cout << "Value Inserted as root node!" << endl;
  39.     } else {
  40.       TreeNode * temp = root;
  41.       while (temp != NULL) {
  42.         if (new_node -> value == temp -> value) {
  43.           cout << "Value Already exist," <<
  44.             "Insert another value!" << endl;
  45.           return;
  46.         } else if ((new_node -> value < temp -> value) && (temp -> left == NULL)) {
  47.           temp -> left = new_node;
  48.           cout << "Value Inserted to the left!" << endl;
  49.           break;
  50.         } else if (new_node -> value < temp -> value) {
  51.           temp = temp -> left;
  52.         } else if ((new_node -> value > temp -> value) && (temp -> right == NULL)) {
  53.           temp -> right = new_node;
  54.           cout << "Value Inserted to the right!" << endl;
  55.           break;
  56.         } else {
  57.           temp = temp -> right;
  58.         }
  59.       }
  60.     }
  61.   }
  62.   void print2D(TreeNode * r, int space) {
  63.     if (r == NULL)
  64.       return;
  65.     space += SPACE;
  66.     print2D(r -> right, space);
  67.     cout << endl;
  68.     for (int i = SPACE; i < space; i++)  
  69.       cout << " ";
  70.     cout << r -> value << "\n";
  71.     print2D(r -> left, space);
  72. }
  73.   TreeNode * recursiveSearch(TreeNode * r, int val) {
  74.     if (r == NULL || r -> value == val)
  75.       return r;
  76.  
  77.     else if (val < r -> value)
  78.       return recursiveSearch(r -> left, val);
  79.  
  80.     else
  81.       return recursiveSearch(r -> right, val);
  82.   }
  83.  
  84.   void printGivenLevel(TreeNode * r, int level) {
  85.     if (r == NULL)
  86.       return;
  87.     else if (level == 0)
  88.       cout << r -> value << " ";
  89.     else
  90.     {
  91.       printGivenLevel(r -> left, level - 1);
  92.       printGivenLevel(r -> right, level - 1);
  93.     }
  94.   }
  95.   TreeNode * minValueNode(TreeNode * node) {
  96.     TreeNode * current = node;
  97.     while (current -> left != NULL) {
  98.       current = current -> left;
  99.     }
  100.     return current;
  101.   }
  102.  
  103.   TreeNode * deleteNode(TreeNode * r, int v) {
  104.    
  105.     if (r == NULL) {
  106.       return NULL;
  107.     }
  108.    
  109.     else if (v < r -> value) {
  110.       r -> left = deleteNode(r -> left, v);
  111.     }
  112.  
  113.     else if (v > r -> value) {
  114.       r -> right = deleteNode(r -> right, v);
  115.     }
  116.    
  117.     else {
  118.      
  119.       if (r -> left == NULL) {
  120.         TreeNode * temp = r -> right;
  121.         delete r;
  122.         return temp;
  123.       } else if (r -> right == NULL) {
  124.         TreeNode * temp = r -> left;
  125.         delete r;
  126.         return temp;
  127.       } else {
  128.    
  129.         TreeNode * temp = minValueNode(r -> right);
  130.      
  131.         r -> value = temp -> value;
  132.      
  133.         r -> right = deleteNode(r -> right, temp -> value);
  134.        
  135.       }
  136.     }
  137.     return r;
  138.   }
  139.  
  140. };
  141.  
  142. int main() {
  143.   BST obj;
  144.   int option, val;
  145. cout << "What operation do you want to perform? " <<
  146.       " Select Option number" << endl;
  147.       cout<<"CHOOSE:"<<endl;
  148.     cout << "1. Insert Node" << endl;
  149.     cout << "2. Search Node" << endl;
  150.     cout << "3. Delete Node" << endl;
  151.     cout << "4. Print" << endl;
  152.     cout << "0. Exit" << endl;
  153.   do {
  154.         cout<<"enter choice:"<<endl;
  155.     cin >> option;
  156.    
  157.     TreeNode * new_node = new TreeNode();
  158.  
  159.     switch (option) {
  160.     case 1:
  161.         cout <<"INSERT"<<endl;
  162.               cout <<"Enter VALUE of TREE NODE to INSERT in BST: ";
  163.               cin >> val;
  164.               new_node->value = val;
  165.               obj.insertNode(new_node);
  166.               cout<<endl;
  167.                 break;
  168.      
  169.     case 2:
  170.       cout << "SEARCH" << endl;
  171.       cout << "Enter VALUE of TREE NODE to SEARCH in BST: ";
  172.       cin >> val;
  173.       new_node = obj.recursiveSearch(obj.root, val);
  174.       if (new_node != NULL) {
  175.         cout << "Value found" << endl;
  176.       } else {
  177.         cout << "Value NOT found" << endl;
  178.       }
  179.       break;
  180.     case 3:
  181.       cout << "DELETE" << endl;
  182.       cout << "Enter VALUE of TREE NODE to DELETE in BST: ";
  183.       cin >> val;
  184.       new_node = obj.recursiveSearch(obj.root, val);
  185.       if (new_node != NULL) {
  186.         obj.deleteNode(obj.root, val);
  187.         cout << "Value Deleted" << endl;
  188.       } else {
  189.         cout << "Value NOT found" << endl;
  190.       }
  191.       break;
  192.     case 4:
  193.       cout << "Tree: " << endl;
  194.       obj.print2D(obj.root, 5);
  195.       cout << endl;
  196.       cout << endl;
  197.       break;
  198.    
  199.     case 0:
  200.      
  201.       break;
  202.     default:
  203.       cout << "Enter Proper Option number " << endl;
  204.     }
  205.  
  206.   } while (option != 0);
  207.  
  208.   return 0;
  209. }