fork download 
  1. #ifndef MyDS_H
  2. #define MyDS_H
  3. #include <iostream>
  4. #include <string>
  5.  
  6.  
  7. class MyDS {
  8. private:
  9.     struct treeNode
  10.     {
  11.         treeNode* left;
  12.         treeNode* right;
  13.         int height;
  14.         std::string data;
  15.         treeNode() {left = NULL; right = NULL;};
  16.         treeNode(const std::string &v, treeNode* l, treeNode* r, int h){data = v; left = l;  right = r; height = h;};
  17.     };
  18.  
  19.     treeNode* root;
  20.     void push(const std::string & n, treeNode * & v);
  21.     bool search( const std::string& s, treeNode * & tree) ;
  22. public:
  23.     MyDS();
  24.     ~MyDS();
  25.     void push(const std::string & n);
  26.     void printPreOrder() const;
  27.     void preOrder(treeNode* pre) const;
  28.     void clear(treeNode* & tree);
  29.     void singleRightRotate(treeNode * & n);
  30.     void doubleRightRotate(treeNode * & n);
  31.     void singleLeftRotate(treeNode * & n);
  32.     void doubleLeftRotate(treeNode * & n);
  33.     bool search(const std::string & s);
  34.     int avlHeight (treeNode * h);
  35.     int max(int v1, int v2);
  36. };
  37. MyDS::MyDS()
  38. {
  39.     root = NULL;
  40.  
  41. }
  42.  
  43. MyDS::~MyDS()
  44. {
  45.     clear(root);
  46. }
  47.  
  48. void MyDS::push(const std::string & n)
  49. {
  50.     push(n,root);
  51. }
  52.  
  53. void MyDS::singleRightRotate(treeNode * & n)
  54. {
  55.     treeNode * temp;
  56.     temp = n->right;
  57.     n->right = temp->left;
  58.     temp->left = n;
  59.     n = temp;
  60.     n->height = max(avlHeight(n->left),avlHeight(n->right)) + 1;
  61.     temp->height = max(n->height,avlHeight(temp->right)) + 1;
  62.  
  63.  
  64. }
  65.  
  66. void MyDS::singleLeftRotate(treeNode * & n)
  67. {
  68.     treeNode * temp;
  69.     temp = n->left;
  70.     n->left = temp->right;
  71.     temp->right = n;
  72.     n = temp;
  73.     n->height = max(avlHeight(n->left),avlHeight(n->right)) + 1;
  74.     temp->height = max(avlHeight(temp->left),n->height) + 1;
  75. }
  76.  
  77. void MyDS::doubleRightRotate(treeNode * & n)
  78. {
  79.     singleLeftRotate(n->right);
  80.     singleRightRotate(n);
  81. }
  82.  
  83. void MyDS::doubleLeftRotate(treeNode * & n)
  84. {
  85.     singleRightRotate(n->left);
  86.     singleLeftRotate(n);
  87. }
  88.  
  89. int MyDS::max(int v1, int v2)
  90. {
  91.     return ((v1 > v2) ? v1 : v2);
  92. }
  93.  
  94. int MyDS::avlHeight(treeNode * h)
  95. {
  96.     int n;
  97.     if( h == NULL)
  98.     {
  99.         return -1;
  100.     }
  101.     else
  102.     {
  103.         n = h->height;
  104.         return n;
  105.     }
  106.  
  107. }
  108.  
  109.  
  110. bool MyDS::search(const std::string& s, treeNode *& tree)
  111. {
  112.     if(tree == NULL)
  113.     {
  114.         return false;
  115.     }
  116.     else if(s < tree->data)
  117.     {
  118.         return search(s, tree->left);
  119.     }
  120.     else if(tree->data < s)
  121.     {
  122.         return search(s, tree->right);
  123.     }
  124.     else
  125.     {
  126.         ;
  127.     }
  128. }
  129.  
  130. bool MyDS::search(const std::string &x)
  131. {
  132.     if (search(x, root)){
  133.         return true;
  134.     }
  135.     else
  136.         return false;
  137. }
  138.  
  139. void MyDS::clear(treeNode* & tree)
  140. {
  141.     if(tree != NULL)
  142.     {
  143.         clear(tree->left);
  144.         clear(tree->right);
  145.         delete tree;
  146.  
  147.     }
  148.  
  149.     tree = NULL;
  150. }
  151.  
  152. void MyDS::push(const std::string & n, treeNode* & v)
  153. {
  154.     if (v == NULL)
  155.     {
  156.         v = new treeNode(n , NULL, NULL, 0);
  157.     }
  158.     else
  159.     {
  160.         if ( n < v->data)
  161.         {
  162.             push(n, v->left);   // goes to left node
  163.  
  164.             if ((avlHeight(v->left) - avlHeight(v->right))==2)
  165.             {
  166.                 if (n < v->left->data)
  167.                 {
  168.                     singleLeftRotate(v);
  169.                 }
  170.                 else
  171.                 {
  172.                     doubleLeftRotate(v);
  173.                 }
  174.             }
  175.         }
  176.         else if ( v->data < n)
  177.         {
  178.             push(n, v->right);  // goes to right node
  179.             if ((avlHeight(v->right) - avlHeight(v->left))==2)
  180.             {
  181.                 if (n > v->right->data)
  182.                 {
  183.                     singleRightRotate(v);
  184.                 }
  185.                 else
  186.                 {
  187.                     doubleRightRotate(v);
  188.                 }
  189.             }
  190.         }
  191.         else
  192.         {
  193.             ; // duplicate; do nothing.
  194.         }
  195.     }
  196.     int a,b,c;
  197.     a = avlHeight(v->left);
  198.     b = avlHeight(v->right);
  199.     c = max(a,b);
  200.     v->height = c + 1;
  201.  
  202. }
  203.  
  204. void MyDS::printPreOrder() const
  205. {
  206.     preOrder(root);
  207. }
  208.  
  209.  
  210. void MyDS::preOrder(treeNode* pre) const
  211. {
  212.     if(pre != NULL)
  213.     {
  214.         std::cout << " " << pre->data << " ";
  215.         preOrder(pre->left);
  216.         preOrder(pre->right);
  217.     }
  218. }
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin 
Standard input is empty
compilation info 
prog.cpp:1:0: error: unterminated #ifndef
 #ifndef MyDS_H
 ^
stdout 
Standard output is empty
https://ideone.com/4CLYzI
language:
C++ (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!