SHARE
TWEET

Untitled

a guest Nov 17th, 2019 71 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. typedef struct node
  5. {
  6.     int key;
  7.     int noChildren;
  8.     struct node* left;
  9.     struct node* right;
  10. }node;
  11.  
  12. node* newNode(int value);
  13. int size(node* root);
  14. node* OS_BUILD_TREE(int values[], node* root, int low, int high);
  15. node* OS_SELECT(node* root, int i);
  16. node* OS_DELETE(node* root, int val);
  17. node* minNode(node* root);
  18. void preOrder(node* root);
  19.  
  20. int main()
  21. {
  22.     int values[] = { 2, 14, 27, 28, 39, 42, 45, 55, 58, 97 };
  23.     int n = sizeof(values) / sizeof(values[0]);
  24.     node* root = NULL;
  25.     root = OS_BUILD_TREE(values, root, 0, n-1);
  26.     preOrder(root);
  27.     cout << '\n';
  28.     node* toSearch = OS_SELECT(root, 5);
  29.     cout << toSearch->key;
  30.     cout << '\n';
  31.     node* toDelete = OS_DELETE(root, 14);
  32.     node* toDelete1 = OS_DELETE(root, 55);
  33.     node* toDelete2 = OS_DELETE(root, 45);
  34.     node* toDelete3 = OS_DELETE(root, 28);
  35.     preOrder(root);
  36. }
  37.  
  38. node* newNode(int value)
  39. {
  40.     node* temp = (node*)malloc(sizeof(node));
  41.     temp->key = value;
  42.     temp->noChildren = 0;
  43.     temp->left = NULL;
  44.     temp->right = NULL;
  45.     return temp;
  46. }
  47.  
  48. int size(node* root)
  49. {
  50.     if (root == NULL)
  51.         return 0;
  52.     else
  53.         return(size(root->left) + size(root->right) + 1);
  54. }
  55.  
  56. node* OS_BUILD_TREE(int values[], node* root, int low, int high)
  57. {
  58.     if (low > high)
  59.     {
  60.         return 0;
  61.     }
  62.     int mid = (low + high) / 2;
  63.     root = newNode(values[mid]);
  64.     root->left = OS_BUILD_TREE(values, root->left, low, mid - 1);
  65.     root->right = OS_BUILD_TREE(values, root->right, mid + 1, high);
  66.     if ((root->left == NULL) && (root->right == NULL))
  67.     {
  68.         root->noChildren = 1;
  69.     }
  70.     else
  71.     {
  72.         root->noChildren = size(root);
  73.     }
  74.     return root;
  75.    
  76. }
  77.  
  78. node* OS_SELECT(node* root, int i)
  79. {
  80.     int left_size;
  81.     if (root->left == NULL)
  82.         left_size = 0;
  83.     else
  84.         left_size = root->left->noChildren;
  85.     if (left_size + 1 == i)
  86.         return root;
  87.     else if (left_size + 1 < i)
  88.         return OS_SELECT(root->right, i - left_size - 1);
  89.     else
  90.         return OS_SELECT(root->left, i);
  91. }
  92.  
  93. node* minNode(node* root)
  94. {
  95.     node* current = root;
  96.     while (current->left != NULL)
  97.     {
  98.         current = current->left;
  99.     }
  100.     return current;
  101. }
  102.  
  103. node* OS_DELETE(node* root, int val)
  104. {
  105.     if (root == NULL)
  106.     {
  107.         return root;
  108.     }
  109.     if (val < root->key)
  110.     {
  111.         root->left = OS_DELETE(root->left, val);
  112.         root->noChildren -= 1;
  113.     }
  114.     else if (val > root->key)
  115.     {
  116.         root->right = OS_DELETE(root->right, val);
  117.         root->noChildren -= 1;
  118.     }
  119.     else
  120.     {
  121.         if (root->left == NULL)
  122.         {
  123.             node* temp = root->right;
  124.             free(root);
  125.             return temp;
  126.             root->noChildren -= 1;
  127.         }
  128.         else if (root->right == NULL)
  129.         {
  130.             node* temp = root->left;
  131.             free(root);
  132.             return temp;
  133.             root->noChildren -= 1;
  134.         }
  135.  
  136.         node* temp = minNode(root->right);
  137.         root->key = temp->key;
  138.         root->right = OS_DELETE(root->right, temp->key);
  139.         root->noChildren -= 1;
  140.     }
  141.     return root;
  142. }
  143.  
  144. void preOrder(node* root)
  145. {
  146.     if (root != NULL)
  147.     {
  148.         cout << root->key << "," << root->noChildren << "   ";
  149.         preOrder(root->left);
  150.         preOrder(root->right);
  151.     }
  152. }
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