SHARE
TWEET

Eheh

a guest Feb 28th, 2020 81 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std ;
  3.  
  4. struct node
  5. {
  6.     int data ;
  7.  
  8.     node *left  ;
  9.     node *right ;
  10.    
  11.     node (int _data)
  12.     {
  13.         data = _data ;
  14.         left = right = NULL ;
  15.     }
  16. };
  17. void printinorder(node *cur)
  18. {
  19.     if(cur == NULL) return ;
  20.     printinorder(cur->left) ;
  21.    
  22.     cout << cur->data << " " ;
  23.  
  24.     printinorder(cur->right) ;
  25. }
  26. void printpreorder(node *cur)
  27. {
  28.     if(cur == NULL) return ;
  29.  
  30.     cout << cur->data << " " ;
  31.  
  32.     printpreorder(cur->left) ;
  33.  
  34.     printpreorder(cur->right) ;
  35. }
  36. void printpostorder(node *cur)
  37. {
  38.     if(cur == NULL) return ;
  39.     printpostorder(cur->left) ;
  40.  
  41.     printpostorder(cur->right) ;
  42.  
  43.     cout << cur->data << " " ;
  44. }
  45. int search(node *cur, int data)
  46. {
  47.     if(cur==NULL) return 0;
  48.     if(cur->data == data) return 1 ;
  49.  
  50.     else if(data <= cur->data) return search(cur->left, data) ;
  51.     else if(data > cur->data) return search(cur->right, data) ;
  52.  
  53.     return 0 ;
  54. }
  55. void insert(node *cur, int _data)
  56. {
  57.     if(_data <= cur->data)
  58.     {
  59.         if(cur->left == NULL)
  60.             cur->left = new node(_data) ;
  61.         else insert(cur->left,_data) ;
  62.     }
  63.     else if(_data > cur->data)
  64.     {
  65.         if(cur->right == NULL)
  66.             cur->right = new node(_data) ;
  67.         else insert(cur->right,_data) ;
  68.     }
  69. }
  70. int UpperBound(node *cur, int _data)
  71. {
  72.     if(_data < cur->data)
  73.     {
  74.         int store = cur->data ;
  75.         if(_data >= cur->left->data || cur->left == NULL) return store ;
  76.         else UpperBound(cur->left,_data) ;
  77.     }
  78.     else if(_data >= cur->data)
  79.     {
  80.         if(_data < cur->right->data)
  81.         {
  82.             int store = cur->right->data ;
  83.             return store ;
  84.         }
  85.         else UpperBound(cur->right,_data) ;
  86.     }
  87. }
  88. int LowerBound(node *cur, int _data)
  89. {
  90.     if(_data <= cur->data)
  91.     {
  92.          if(_data > cur->left->data)
  93.          {
  94.             cur = cur->left ;
  95.             if(cur->right == NULL) return cur->data ;
  96.             while(cur != NULL) {
  97.                 cur = cur->right ;
  98.                 if(cur->right == NULL)
  99.                 {
  100.                     int store = cur->data ;
  101.                     return store ;
  102.                 }
  103.          }
  104.          }
  105.          else LowerBound(cur->left,_data) ;
  106.     }
  107.     else if(_data > cur->data)
  108.     {
  109.         if(_data < cur->right->data)
  110.         {
  111.            return cur->data ;
  112.         }
  113.         else if(_data == cur->right->data)
  114.         {
  115.             int store = cur->data ;
  116.             cur = cur->right ;
  117.             int store1 = cur->left->data ;
  118.             if(store <= store1) return store ;
  119.             else return store1 ;
  120.         }
  121.         else LowerBound(cur->right,_data) ;
  122.  
  123.     }
  124. }
  125. int main(int argc, char const *argv[])
  126. {
  127.     struct node *root =new node(4)  ;
  128.     root->left = new node(2) ;
  129.     root->right = new node(6) ;
  130.     root->left->left = new node(1) ;
  131.     root->left->right = new node(3) ;
  132.     root->right->left = new node(5) ;
  133.     root->right->right = new node(9) ;
  134.     printpreorder(root) ;
  135.     cout  << endl ;
  136.     printinorder(root) ;
  137.     cout << endl ;
  138.     printpostorder(root) ;
  139.     cout << endl ;
  140.     insert(root,9) ;
  141.     insert(root,10) ;
  142.     insert(root,12) ;
  143.     insert(root,17) ;
  144.     insert(root,17) ;
  145.     insert(root,-12) ;
  146.     insert(root,-37) ;
  147.     insert(root,-7) ;
  148.     insert(root,-3) ;
  149.     insert(root,2) ;
  150.     insert(root,3) ;
  151.     printinorder(root) ;
  152.     cout << endl ;
  153.     int val = search(root,-71) ;
  154.     if(val == 1) cout <<  " Found " << endl ;
  155.     else cout <<  "Not Found " << endl ;
  156. //   cout << endl ;
  157.     cout << UpperBound(root,-37) << endl ;
  158.     cout << LowerBound(root,-37) << endl ;
  159.     return 0;
  160. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top