Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <stdlib.h>
- #include <math.h>
- #include <string.h>
- #include <ctype.h>
- typedef struct node {
- char* key;
- struct node *left;
- struct node *right;
- int height;
- }node;
- void preOrder(node *root)
- {
- if(root == NULL)
- return;
- printf("%sn", root->key);
- preOrder(root->left);
- preOrder(root->right);
- }
- int max(int a, int b);
- // A utility function to get height of the tree
- int height(node* N)
- {
- if(N==NULL)
- return 0;
- return N->height;
- }
- // A utility function to get maximum of two integers
- int max(int a, int b)
- {
- if(a > b)
- {
- return a;
- }
- else
- return b;
- }
- int avlHeight(node* N) {
- if(N == NULL)
- return -1;
- else
- return max(height(N->left), height(N->right)) + 1;
- }
- int nodeCount(node *root)
- {
- int count = 0;
- if (root != NULL) {
- count = 1 + nodeCount(root->left) + nodeCount(root->right);
- }
- return count;
- }
- /* Helper function that allocates a new node with the given key and
- NULL left and right pointers. */
- node* newNode(node* node, char* key)
- {
- struct node* node2 = (struct node*)malloc(sizeof(struct node));
- node2->key = key;
- node2->left = NULL;
- node2->right = NULL;
- node2->height = 1; // new node is initially added at leaf
- return(node2);
- }
- // A utility function to right rotate subtree rooted with y
- // See the diagram given above.
- node *rightRotate(node *y)
- {
- node *x = y->left;
- node *T2 = x->right;
- // Perform rotation
- x->right = y;
- y->left = T2;
- // Update heights
- y->height = max(height(y->left), height(y->right))+1;
- x->height = max(height(x->left), height(x->right))+1;
- // Return new root
- return x;
- }
- // A utility function to left rotate subtree rooted with x
- // See the diagram given above.
- node *leftRotate(node *x)
- {
- printf("3rdn");
- node *y = x->right;
- node *T2 = y->left;
- // Perform rotation
- y->left = x;
- x->right = T2;
- // Update heights
- x->height = max(height(x->left), height(x->right))+1;
- y->height = max(height(y->left), height(y->right))+1;
- // Return new root
- return y;
- }
- // Get Balance factor of node N
- int getBalance(node *N)
- {
- if (N == NULL)
- return 0;
- return height(N->left) - height(N->right);
- }
- node* insert(node* node, char* key)
- {
- /* 1. Perform the normal BST rotation */
- if (node == NULL)
- return(newNode(node, key));
- if (strcmp(key, node->key) < 0) {
- node->left = insert(node->left, key);
- }
- else {
- node->right = insert(node->right, key);
- }
- /* 2. Update height of this ancestor node */
- //node->height = max(height(node->left), height(node->right)) + 1;
- //printf("%d ",node->height);
- /* 3. Get the balance factor of this ancestor node to check whether
- this node became unbalanced */
- //int balance = getBalance(node);
- // If this node becomes unbalanced, then there are 4 cases
- // Left Left Case
- /*if (balance > 1 && strcmp(key, (node->left)->key)<0){
- printf("1stn");
- return rightRotate(node);
- }
- // Right Right Case
- if (balance < -1 && strcmp(key, (node->right)->key)>0){
- printf("2ndn");
- return leftRotate(node);
- }
- // Left Right Case
- //i = strcmp(key, (node->left)->key);
- //printf("!%d!",i);
- if (balance > 1 && strcmp(key, (node->left)->key)>0){
- printf("3rdn");
- node->left = leftRotate(node->left);
- return rightRotate(node);
- }
- // Right Left Case
- if (balance < -1 && strcmp(key, node->right->key)<0)
- {
- printf("4thn");
- node->right = rightRotate(node->right);
- return leftRotate(node);
- }
- /* return the (unchanged) node pointer */
- //printf("%s ",key);
- //preOrder(node);
- return node;
- }
- // A utility function to print preorder traversal of the tree.
- // The function also prints height of every node
- void nick() {//initial banner addition
- printf("**********************************************************n");
- printf("Welcome to the Arethmatic Expression calculator!n");
- printf("Created by: Nicholas Bastiann");
- printf("Student ID #: 0843261n");
- printf("**********************************************************nn");
- }
- void menu()//menu function
- {
- printf("nWhat would you like to do? (Please input a single number)n");
- printf("1. Initializationn");
- printf("2. Findn");
- printf("3. Insertn");
- printf("4. Removen");
- printf("5. Check Height and Sizen");
- printf("6. Find All (above a given frequency)n");
- printf("7. Exitn");
- printf("avl/> ");
- }
- int main()
- {
- char value[100];
- char str[100];
- int counter = 1, choice, height, size;
- char*token, *key;//, *flr239='endnue783', *ene039='irhwr32';
- node* root= NULL;
- static const char input[] = "avl.dat";//"A4_data_file.dat";
- FILE* textFile = fopen(input,"r");
- while(fgets(str, 100, textFile)) {
- token = strtok(str," n");
- while (token != NULL)
- {
- key = strdup(token);
- root = insert(root, key);
- free(key);
- token = strtok (NULL, " n");
- }
- if(ferror(textFile))
- {
- printf("you done fucked up a-a-ron");
- return(0);
- }
- }
- nick();
- do{
- menu();
- fgets(value,100,stdin);
- choice = atoi(value);//user proofed menu
- switch(choice)
- {
- case 1:
- printf("filename: ");
- printf("Pre order traversal of the constructed AVL tree is n");
- preOrder(root);
- break;
- case 2:
- /*printf("findkey: %s");
- printf(", frequency: %d");*/
- break;
- case 3:
- printf("insert key: ");
- break;
- case 4:
- printf("remove key: ");
- break;
- case 5:
- height = avlHeight(root);
- size = nodeCount(root);
- printf("height: %d", height);
- printf(", size: %d", size);
- break;
- case 6:
- printf("frequency: ");
- break;
- case 7:
- printf("Exiting program...n");
- exit(0);
- break;
- default:
- printf("nPlease put input a number from 1 to 7 (only a single integer).nn");
- break;
- }
- }while(counter==1);
- return(0);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement