Friday 30 September 2016

Binary Search Tree: Search for key element

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