Binary Search Tree implementation in C
Binary Search Tree is tree which two nodes left and right for every node. Let us implement it in C language.
It has following functions.
Creating node
Adding elements
Searching an element.
In order traversal.
Code:
#include <stdio.h>
#include <stdlib.h>
struct bst_Node {
int key;
struct bst_Node*
left;
struct bst_Node*
right;
};
// Let us Create a new node
struct bst_Node* createNode(int key) {
struct bst_Node*
newNode1 = (struct bst_Node*)malloc(sizeof(struct bst_Node));
newNode1->key =
key;
newNode1->left
= newNode1->right = NULL;
return newNode1;
}
// Add a node
struct bst_Node* insert(struct bst_Node* root, int key) {
if (root == NULL)
return createNode(key);
if (key <
root->key)
root->left
= insert(root->left, key);
else if (key >
root->key)
root->right
= insert(root->right, key);
return root;
}
// Search a particular node
struct bst_Node* search(struct bst_Node* root, int key) {
if (root == NULL
|| root->key == key) return root;
if (key <
root->key)
return
search(root->left, key);
return
search(root->right, key);
}
// Code for In-order traversal
void inorder(struct bst_Node* root) {
if (root != NULL)
{
inorder(root->left);
printf("%d ", root->key);
inorder(root->right);
}
}
int main() {
struct bst_Node*
root = NULL;
// add values
to nodes
int values[] =
{60, 23, 67, 10, 34, 76, 90};
int n =
sizeof(values) / sizeof(values[0]);
int target =0;
for (int i = 0; i
< n; i++) {
root =
insert(root, values[i]);
}
printf("Inorder traversal: ");
inorder(root);
printf("\n");
// Search for a
value
printf("Enter
the value to search");
scanf("%d",&target);
struct bst_Node*
found = search(root, target);
if (found != NULL)
printf("The node %d is found in BST.\n", target);
else
printf("%d not found in BST.\n", target);
return 0;
}
Output:
Inorder traversal: 10 23 34 60 67 76 90
Enter the value to search67
The node 67 is found in BST.
Inorder traversal: 10 23 34 60 67 76 90
Enter the value to search12
12 not found in BST.
Thus, the implementation of Binary Search Tree in c language
was done. Hope, this code is useful to you. Keep Coding!!!
Comments
Post a Comment