Created
February 18, 2024 03:20
-
-
Save shahzaib-sheikh/15b83dac831e2dbb1af4fa4c8d5caa16 to your computer and use it in GitHub Desktop.
Tree Implementation in C
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <stdio.h> | |
| #include <stdlib.h> | |
| typedef struct Node | |
| { | |
| int data; | |
| struct Node *right; | |
| struct Node *left; | |
| int count; | |
| } Node; | |
| typedef struct Tree | |
| { | |
| int nodesCount; | |
| Node *root; | |
| } Tree; | |
| Node *initializeNode(); | |
| Tree *initializeTree(); | |
| void printTree(Tree *tptr); | |
| void printTreeFromNode(Node *nptr, int order); | |
| void insertIntoTree(Tree *tptr, int data); | |
| int insertIntoTreeRecursive(Tree *tptr, int data); | |
| int insertIntoTreeByNodeRecursive(Node *nptr, int data, Node **toBeUpdated); | |
| Node *searchInTree(Tree *tptr, int data); | |
| int mod(int number); | |
| Node *getMinimumNodeAddress(Node **nptr, int detach); | |
| int main() | |
| { | |
| Tree *tptr = initializeTree(); | |
| getchar(); | |
| // insertIntoTree(tptr, 56); | |
| // insertIntoTree(tptr, 76); | |
| // insertIntoTree(tptr, 89); | |
| // insertIntoTree(tptr, 45); | |
| // insertIntoTree(tptr, 12); | |
| // insertIntoTree(tptr, 213); | |
| // insertIntoTree(tptr, 134); | |
| // insertIntoTree(tptr, -65); | |
| // insertIntoTree(tptr, 423); | |
| // insertIntoTree(tptr, 32); | |
| // insertIntoTree(tptr, 7); | |
| insertIntoTreeRecursive(tptr, 56); | |
| insertIntoTreeRecursive(tptr, 76); | |
| insertIntoTreeRecursive(tptr, 89); | |
| insertIntoTreeRecursive(tptr, 45); | |
| insertIntoTreeRecursive(tptr, 12); | |
| insertIntoTreeRecursive(tptr, 213); | |
| insertIntoTreeRecursive(tptr, 134); | |
| insertIntoTreeRecursive(tptr, -65); | |
| insertIntoTreeRecursive(tptr, 423); | |
| insertIntoTreeRecursive(tptr, 32); | |
| insertIntoTreeRecursive(tptr, 7); | |
| printTree(tptr); | |
| // deleteFromTree(tptr,32); | |
| deleteFromTree(tptr, 56); | |
| // deleteFromTree(tptr,89); | |
| // deleteFromTree(tptr,7); | |
| deleteFromTree(tptr, -65); | |
| // deleteFromTree(tptr,12); | |
| deleteFromTree(tptr, 76); | |
| // deleteFromTree(tptr,45); | |
| // deleteFromTree(tptr,134); | |
| deleteFromTree(tptr, 213); | |
| // deleteFromTree(tptr,423); | |
| // printTree(tptr); | |
| printTree(tptr); | |
| searchInTree(tptr, 56); | |
| searchInTree(tptr, 45); | |
| searchInTree(tptr, 134); | |
| } | |
| void printTree(Tree *tptr) | |
| { | |
| puts("\tPrinting Tree"); | |
| printTreeFromNode(tptr->root, 1); | |
| } | |
| int mod(int number) | |
| { | |
| if (number < 0) | |
| { | |
| return number * -1; | |
| } | |
| return number; | |
| } | |
| int insertIntoTreeRecursive(Tree *tptr, int data) | |
| { | |
| tptr->nodesCount++; | |
| return insertIntoTreeByNodeRecursive(tptr->root, data, &tptr->root); | |
| } | |
| int deleteFromTree(Tree *tptr, int data) | |
| { | |
| if (tptr->root == NULL) | |
| { | |
| puts("\nEmpty Tree"); | |
| return 0; | |
| } | |
| Node *temp = tptr->root; | |
| Node **toBeUpdatedPrevious = &tptr->root; | |
| while (temp != NULL) | |
| { | |
| if (temp->data == data) | |
| { | |
| if (temp->count > 1) | |
| { | |
| temp->count--; | |
| return 1; | |
| } | |
| break; | |
| } | |
| if (temp->data > data) | |
| { | |
| toBeUpdatedPrevious = &temp->left; | |
| temp = temp->left; | |
| } | |
| else | |
| { | |
| toBeUpdatedPrevious = &temp->right; | |
| temp = temp->right; | |
| } | |
| } | |
| if (temp == NULL) | |
| { | |
| puts("\nvalue not found"); | |
| return 0; | |
| } | |
| if (temp->right == NULL) | |
| { | |
| *toBeUpdatedPrevious = temp->left; | |
| free(temp); | |
| return 1; | |
| } | |
| Node *minimum = getMinimumNodeAddress(&temp->right, 1); | |
| minimum->left = temp->left; | |
| minimum->right = temp->right; | |
| *toBeUpdatedPrevious = minimum; | |
| free(temp); | |
| return 1; | |
| } | |
| Node *getMinimumNodeAddress(Node **nptr, int detach) | |
| { | |
| Node *current = *nptr; | |
| Node **tobeUpdated = nptr; | |
| int check = 0; | |
| while (1) | |
| { | |
| if (current->left != NULL) | |
| { | |
| tobeUpdated = ¤t->left; | |
| current = current->left; | |
| check = 1; | |
| } | |
| else | |
| { | |
| if (detach && check) | |
| { | |
| *tobeUpdated = NULL; | |
| } | |
| else | |
| { | |
| *tobeUpdated = current->right; | |
| } | |
| return current; | |
| } | |
| } | |
| } | |
| int insertIntoTreeByNodeRecursive(Node *nptr, int data, Node **toBeUpdated) | |
| { | |
| if (nptr == NULL) | |
| { | |
| Node *temp = initializeNode(); | |
| temp->data = data; | |
| *toBeUpdated = temp; | |
| return 1; | |
| } | |
| else | |
| { | |
| if (nptr->data == data) | |
| { | |
| nptr->count++; | |
| return 1; | |
| } | |
| if (nptr->data > data) | |
| { | |
| insertIntoTreeByNodeRecursive(nptr->left, data, &nptr->left); | |
| } | |
| else | |
| { | |
| insertIntoTreeByNodeRecursive(nptr->right, data, &nptr->right); | |
| } | |
| return 1; | |
| } | |
| } | |
| Node *searchInTree(Tree *tptr, int data) | |
| { | |
| if (tptr->root == NULL) | |
| { | |
| puts("\nEmpty Tree"); | |
| return NULL; | |
| } | |
| Node *temp = tptr->root; | |
| while (temp != NULL) | |
| { | |
| if (temp->data == data) | |
| { | |
| puts("\nvalue found"); | |
| if (temp == tptr->root) | |
| { | |
| puts("root node"); | |
| } | |
| else if (temp->left == NULL && temp->right == NULL) | |
| { | |
| puts("leaf node"); | |
| } | |
| else | |
| { | |
| puts("internal node"); | |
| } | |
| printf("\ndata=>%d \taddress=>%d \tleft=>%d \tright=>%d \tcount=>%d ", temp->data, temp, temp->left, temp->right, temp->count); | |
| return temp; | |
| } | |
| if (temp->data > data) | |
| { | |
| temp = temp->left; | |
| } | |
| else | |
| { | |
| temp = temp->right; | |
| } | |
| } | |
| puts("\nvalue not found"); | |
| return NULL; | |
| } | |
| void printTreeFromNode(Node *nptr, int order) | |
| { | |
| if (nptr == NULL) | |
| { | |
| return; | |
| } | |
| // preorder | |
| if (order == 1) | |
| { | |
| printTreeFromNode(nptr->left, order); | |
| printf("\ndata=>%d \taddress=>%d \tleft=>%d \tright=>%d \tcount=>%d ", nptr->data, nptr, nptr->left, nptr->right, nptr->count); | |
| printTreeFromNode(nptr->right, order); | |
| return; | |
| } | |
| // inorder | |
| if (order == 2) | |
| { | |
| printf("\ndata=>%d \taddress=>%d \tleft=>%d \tright=>%d \tcount=>%d ", nptr->data, nptr, nptr->left, nptr->right, nptr->count); | |
| printTreeFromNode(nptr->left, order); | |
| printTreeFromNode(nptr->right, order); | |
| return; | |
| } | |
| // postorder | |
| if (order == 3) | |
| { | |
| printTreeFromNode(nptr->left, order); | |
| printTreeFromNode(nptr->right, order); | |
| printf("\ndata=>%d \taddress=>%d \tleft=>%d \tright=>%d \tcount=>%d ", nptr->data, nptr, nptr->left, nptr->right, nptr->count); | |
| return; | |
| } | |
| } | |
| Tree *initializeTree() | |
| { | |
| Tree *ptr = (Tree *)malloc(sizeof(Tree)); | |
| ptr->nodesCount = 0; | |
| ptr->root = NULL; | |
| return ptr; | |
| } | |
| void insertIntoTree(Tree *tptr, int data) | |
| { | |
| if (tptr->root == NULL) | |
| { | |
| tptr->root = initializeNode(); | |
| tptr->root->data = data; | |
| tptr->root->count++; | |
| } | |
| else | |
| { | |
| Node *temp = tptr->root; | |
| Node *previous = NULL; | |
| while (temp != NULL) | |
| { | |
| if (temp->data == data) | |
| { | |
| temp->count++; | |
| return; | |
| } | |
| previous = temp; | |
| if (temp->data > data) | |
| { | |
| temp = temp->left; | |
| } | |
| else | |
| { | |
| temp = temp->right; | |
| } | |
| } | |
| Node *newNode = initializeNode(); | |
| newNode->data = data; | |
| newNode->count++; | |
| if (previous->data > data) | |
| { | |
| previous->left = newNode; | |
| } | |
| else | |
| { | |
| previous->right = newNode; | |
| } | |
| tptr->nodesCount++; | |
| } | |
| } | |
| Node *initializeNode() | |
| { | |
| Node *ptr = (Node *)malloc(sizeof(Node)); | |
| ptr->data = 0; | |
| ptr->right = NULL; | |
| ptr->left = NULL; | |
| ptr->count = 0; | |
| return ptr; | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment