Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- using namespace std;
- typedef struct node
- {
- int key;
- int noChildren;
- struct node* left;
- struct node* right;
- }node;
- node* newNode(int value);
- int size(node* root);
- node* OS_BUILD_TREE(int values[], node* root, int low, int high);
- node* OS_SELECT(node* root, int i);
- node* OS_DELETE(node* root, int val);
- node* minNode(node* root);
- void preOrder(node* root);
- int main()
- {
- int values[] = { 2, 14, 27, 28, 39, 42, 45, 55, 58, 97 };
- int n = sizeof(values) / sizeof(values[0]);
- node* root = NULL;
- root = OS_BUILD_TREE(values, root, 0, n-1);
- preOrder(root);
- cout << '\n';
- node* toSearch = OS_SELECT(root, 5);
- cout << toSearch->key;
- cout << '\n';
- node* toDelete = OS_DELETE(root, 14);
- node* toDelete1 = OS_DELETE(root, 55);
- node* toDelete2 = OS_DELETE(root, 45);
- node* toDelete3 = OS_DELETE(root, 28);
- preOrder(root);
- }
- node* newNode(int value)
- {
- node* temp = (node*)malloc(sizeof(node));
- temp->key = value;
- temp->noChildren = 0;
- temp->left = NULL;
- temp->right = NULL;
- return temp;
- }
- int size(node* root)
- {
- if (root == NULL)
- return 0;
- else
- return(size(root->left) + size(root->right) + 1);
- }
- node* OS_BUILD_TREE(int values[], node* root, int low, int high)
- {
- if (low > high)
- {
- return 0;
- }
- int mid = (low + high) / 2;
- root = newNode(values[mid]);
- root->left = OS_BUILD_TREE(values, root->left, low, mid - 1);
- root->right = OS_BUILD_TREE(values, root->right, mid + 1, high);
- if ((root->left == NULL) && (root->right == NULL))
- {
- root->noChildren = 1;
- }
- else
- {
- root->noChildren = size(root);
- }
- return root;
- }
- node* OS_SELECT(node* root, int i)
- {
- int left_size;
- if (root->left == NULL)
- left_size = 0;
- else
- left_size = root->left->noChildren;
- if (left_size + 1 == i)
- return root;
- else if (left_size + 1 < i)
- return OS_SELECT(root->right, i - left_size - 1);
- else
- return OS_SELECT(root->left, i);
- }
- node* minNode(node* root)
- {
- node* current = root;
- while (current->left != NULL)
- {
- current = current->left;
- }
- return current;
- }
- node* OS_DELETE(node* root, int val)
- {
- if (root == NULL)
- {
- return root;
- }
- if (val < root->key)
- {
- root->left = OS_DELETE(root->left, val);
- root->noChildren -= 1;
- }
- else if (val > root->key)
- {
- root->right = OS_DELETE(root->right, val);
- root->noChildren -= 1;
- }
- else
- {
- if (root->left == NULL)
- {
- node* temp = root->right;
- free(root);
- return temp;
- root->noChildren -= 1;
- }
- else if (root->right == NULL)
- {
- node* temp = root->left;
- free(root);
- return temp;
- root->noChildren -= 1;
- }
- node* temp = minNode(root->right);
- root->key = temp->key;
- root->right = OS_DELETE(root->right, temp->key);
- root->noChildren -= 1;
- }
- return root;
- }
- void preOrder(node* root)
- {
- if (root != NULL)
- {
- cout << root->key << "," << root->noChildren << " ";
- preOrder(root->left);
- preOrder(root->right);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement