Binary Search Tree: Search for key element
#include<stdio.h>
#include<stdlib.h>
struct BST
{
int
data;
struct
BST *lchild;
struct
BST *rchild;
};
typedef struct BST * NODE;
NODE get_node()
{
NODE
temp;
temp
= (NODE) malloc(sizeof(struct BST));
temp->lchild
= NULL;
temp->rchild
= NULL;
return
temp;
}
void insert(NODE root, NODE newnode)
{
if
(newnode->data < root->data)
{
if
(root->lchild == NULL)
root->lchild
= newnode;
else
insert(root->lchild,
newnode);
}
if
(newnode->data > root->data)
{
if
(root->rchild == NULL)
root->rchild
= newnode;
else
insert(root->rchild,
newnode);
}
}
void search(NODE root, int key)
{
NODE
cur;
if(root == NULL)
{
printf("\nBST
is empty.");
return;
}
cur
= root;
while
(cur != NULL)
{
if
(cur->data == key)
{
printf("\nKey
element %d is present in BST", cur->data);
return;
}
if (key <
cur->data)
cur
= cur->lchild;
else
cur
= cur->rchild;
}
printf("\nKey
element %d is not found in the BST", key);
}
void main()
{
int val, i, n, key;
NODE
root = NULL, newnode;
printf("\nEnter the
number of elements: ");
scanf("%d", &n);
for(i=1;i<=n;i++)
{
newnode
= get_node();
printf("\nEnter
The node value: ");
scanf("%d",
&val);
newnode->data
= val;
if
(root == NULL)
root
= newnode;
else
insert(root,
newnode);
}
/*Search for a given key in BST*/
printf("\nEnter
Element to be searched: ");
scanf("%d",
&key);
search(root, key);
}
Case 1:
Enter the number of elements: 12
Enter The node value: 6
Enter The node value: 9
Enter The node value: 5
Enter The node value: 2
Enter The node value: 8
Enter The node value: 15
Enter The node value: 24
Enter The node value: 14
Enter The node value: 7
Enter The node value: 8
Enter The node value: 5
Enter The node value: 2
Enter
Element to be searched: 66
Key
element 66 is not found in the BST
Case 2:
Enter the number of elements: 12
Enter The node value: 6
Enter The node value: 9
Enter The node value: 5
Enter The node value: 2
Enter The node value: 8
Enter The node value: 15
Enter The node value: 24
Enter The node value: 14
Enter The node value: 7
Enter The node value: 8
Enter The node value: 5
Enter The node value: 2
Enter
Element to be searched: 5
Key
element 5 is present in BST
No comments:
Post a Comment