Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <stdlib.h>
- #define max(a, b) ({ __typeof__ (a) _a = (a); __typeof__ (b) _b = (b); _a > _b ? _a : _b; })
- struct Node {
- int key, height;
- struct Node *left, *right;
- };
- int height(struct Node *N) {
- if (N == NULL)
- return 0;
- return N->height;
- }
- struct Node *newNode(int key) {
- struct Node* node = (struct Node*)
- malloc(sizeof(struct Node));
- node->key = key;
- node->left = NULL;
- node->right = NULL;
- node->height = 1;
- return(node);
- }
- struct Node *rightRotate(struct Node *y) {
- struct Node *x = y->left;
- struct Node *T2 = x->right;
- x->right = y;
- y->left = T2;
- y->height = max(height(y->left), height(y->right))+1;
- x->height = max(height(x->left), height(x->right))+1;
- return x;
- }
- struct Node *leftRotate(struct Node *x) {
- struct Node *y = x->right;
- struct Node *T2 = y->left;
- y->left = x;
- x->right = T2;
- x->height = max(height(x->left), height(x->right))+1;
- y->height = max(height(y->left), height(y->right))+1;
- return y;
- }
- int getBalance(struct Node *N) {
- if (N == NULL)
- return 0;
- return height(N->left) - height(N->right);
- }
- struct Node *Balance(struct Node *node, int balance, int key) {
- if (balance > 1 && key < node->left->key)
- return rightRotate(node);
- // Right Right Case
- if (balance < -1 && key > node->right->key)
- return leftRotate(node);
- // Left Right Case
- if (balance > 1 && key > node->left->key) {
- node->left = leftRotate(node->left);
- return rightRotate(node);
- }
- // Right Left Case
- if (balance < -1 && key < node->right->key) {
- node->right = rightRotate(node->right);
- return leftRotate(node);
- }
- return node;
- }
- struct Node* insert(struct Node* node, int key) {
- if (node == NULL)
- return(newNode(key));
- if (key < node->key)
- node->left = insert(node->left, key);
- else if (key > node->key)
- node->right = insert(node->right, key);
- else
- return node;
- node->height = 1 + max(height(node->left), height(node->right));
- int balance = getBalance(node);
- node = Balance(node, balance, key);
- return node;
- }
- struct Node * minValueNode(struct Node* node) {
- struct Node* current = node;
- while (current->left != NULL)
- current = current->left;
- return current;
- }
- struct Node* deleteNode(struct Node* root, int key) {
- if (root == NULL)
- return root;
- if ( key < root->key )
- root->left = deleteNode(root->left, key);
- else if( key > root->key )
- root->right = deleteNode(root->right, key);
- else {
- // node with only one child or no child
- if( (root->left == NULL) || (root->right == NULL) ) {
- struct Node *temp = root->left ? root->left : root->right;
- if (temp == NULL) {
- temp = root;
- root = NULL;
- } else {
- *root = *temp;
- }
- free(temp);
- } else {
- struct Node* temp = minValueNode(root->right);
- root->key = temp->key;
- root->right = deleteNode(root->right, temp->key);
- }
- }
- if (root == NULL)
- return root;
- root->height = 1 + max(height(root->left), height(root->right));
- int balance = getBalance(root);
- root = Balance(root, balance, key);
- return root;
- }
- void print(struct Node *root, int o) {
- if(root != NULL) {
- if(o == 1) printf("%d ", root->key);
- print(root->left, o);
- if(o == 2) printf("%d ", root->key);
- print(root->right, o);
- if(o == 3) printf("%d ", root->key);
- }
- }
- int fastio(char num[]){
- int negative = 0, i = 0, number = 0;
- if (num[0] == '-'){
- negative = 1;
- i++;
- }
- for (; num[i] >= 48 && num[i] <= 57 && num[i]; i++)
- number = number * 10 + num[i] - 48;
- if (negative)
- number *= -1;
- return number;
- }
- int main() {
- struct Node *root = NULL;
- long long int x, z;
- char k[100];
- printf("\t\t[MENU]\n_______________________________________\n1 - inserir\n2 - remover\n3 - printar\n0 - sair\n\n"
- "Caso 1 ou 2:\nX para sair\n\nCaso 3:\n1 - preOrder 2 - inOrder 3 - postOrder\n_______________________________________\n\n");
- while(scanf("%lld", &x), x){
- switch(x){
- case 1:
- while(scanf("%s", k), (k[0] != 'x' && k[0] != 'X')){
- z = fastio(k);
- root = insert(root, z);
- }
- break;
- case 2:
- while(scanf("%s", k), (k[0] != 'x' && k[0] != 'X')){
- z = fastio(k);
- root = deleteNode(root, z);
- }
- break;
- case 3:
- scanf("%lld", &z);
- printf("%s: ", z == 1 ? "preOrder\0" : (z == 2 ? "inOrder\0" : "postOrder\0"));
- print(root, z);
- printf("\n");
- break;
- }
- }
- free(root);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement