Last active
November 20, 2018 16:45
-
-
Save jamesgeorge007/22aee978ce2cb93a506d278f7343dc6c to your computer and use it in GitHub Desktop.
Binary Search Tree operations in C.
This file contains 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> | |
struct Node | |
{ | |
int data; | |
struct Node* next; | |
struct Node* prev; | |
}; | |
struct Node *root = NULL; | |
struct Node *temp = NULL; | |
void insert_succ(struct Node* node) | |
{ | |
if((temp->data > node->data) && (node->next != NULL)) | |
insert_succ(node->next); | |
else if((temp->data > node->data) && (node->next == NULL)) | |
node->next = temp; | |
if((temp->data < node->data) && (node->prev != NULL)) | |
insert_succ(node->prev); | |
else if((temp->data < node->data) && (node->prev == NULL)) | |
node->prev = temp; | |
} | |
void insertNode() | |
{ | |
int el; | |
temp = (struct Node*)malloc(sizeof(struct Node)); | |
printf("\nData to be inserted into the node: "); | |
scanf("%d", &el); | |
temp->data = el; | |
temp->next = temp->prev = NULL; | |
if(root == NULL) | |
root = temp; | |
else | |
insert_succ(root); | |
} | |
void preorder(struct Node* node) | |
{ | |
if(node == NULL) | |
{ | |
printf("\nTree is empty!"); | |
exit(1); | |
} | |
printf("%d =>", node->data); | |
if(node->prev != NULL) | |
preorder(node->prev); | |
if(node->next != NULL) | |
preorder(node->next); | |
} | |
void inorder(struct Node *node) | |
{ | |
if (root == NULL) | |
{ | |
printf("No elements in a tree to display"); | |
return; | |
} | |
if (node->prev != NULL) | |
inorder(node->prev); | |
printf("%d => ", node->data); | |
if (node->next != NULL) | |
inorder(node->next); | |
} | |
void postorder(struct Node* node) | |
{ | |
if(node == NULL) | |
{ | |
printf("\nTree is empty!"); | |
exit(1); | |
} | |
if(node->prev != NULL) | |
postorder(node->prev); | |
if(node->next != NULL) | |
postorder(node->next); | |
printf("%d =>", node->data); | |
} | |
void search_el(struct Node* node, int el) | |
{ | |
if(root == NULL) | |
{ | |
printf("\nTree is empty!"); | |
exit(1); | |
} | |
// Since the method is being invoked recursively, node becomes null if the element is not found. | |
if(node == NULL) | |
{ | |
printf("\nElement not found!"); | |
return; | |
} | |
if(el < node->data) | |
search_el(node->prev, el); | |
else if(el > node->data) | |
search_el(node->next, el); | |
else if(el == node->data) | |
{ | |
printf("\nElement found!"); | |
} | |
} | |
struct Node* find_succ(struct Node* node) | |
{ | |
while(node->prev != NULL) | |
{ | |
node = node->prev; | |
} | |
return node; | |
} | |
struct Node* deleteNode(struct Node* root, int el) | |
{ | |
struct Node* temp_node; | |
if(root == NULL) | |
{ | |
printf("\nTree is empty!"); | |
exit(1); | |
} | |
else if(el > root->data) | |
root->next = deleteNode(root->next, el); | |
else if(el < root->data) | |
root->prev = deleteNode(root->prev, el); | |
else | |
{ | |
if(root->next == NULL && root->prev == NULL) | |
{ | |
free(root); | |
root = NULL; | |
} | |
else if(root->prev == NULL) | |
{ | |
temp_node = root; | |
root = root->next; | |
free(temp_node); | |
} | |
else | |
{ | |
temp_node = find_succ(root->next); | |
root->data = temp_node->data; | |
root->next = deleteNode(root->next, temp_node->data); | |
} | |
} | |
return root; | |
} | |
int main() | |
{ | |
int el, cont = 1; | |
while(1) | |
{ | |
insertNode(); | |
printf("\nWant to continue? Enter 1 for Yes: "); | |
scanf("%d", &cont); | |
if(cont != 1) | |
break; | |
} | |
printf("\nPreorder form: "); | |
preorder(root); | |
printf("\nInorder form: "); | |
inorder(root); | |
printf("\nPostorder form: "); | |
postorder(root); | |
printf("\nData of the node to be searched: "); | |
scanf("%d", &el); | |
search_el(root, el); | |
printf("\nData of the node to be deleted: "); | |
scanf("%d", &el); | |
deleteNode(root, el); | |
printf("\nTree after deleting %d is: ", el); | |
preorder(root); | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment