C program for searching a Node in List | Link List Searching in C

C program for searching a Node in List | Link List Searching in C

Data values are given which we call a key and a binary search tree. To search for the key in the given binary search tree, start with the root node and compare the key with the data value of the root node. If they match, return the root pointer. If the key is less than the data value of the root node, repeat the process by using the left subtree. Otherwise, repeat the same process with the right subtree until either a match is found or the subtree under consideration becomes an empty tree.

#include 
#include 
struct tnode
{
  int data;
  struct tnode *lchild, *rchild;
};
/* A function to serch for a given data value in a binary search tree*/
struct tnode *search( struct tnode *p,int key)
   {
     struct tnode *temp;
      temp = p;
     while( temp != NULL)
       {
         if(temp->data == key)
                return(temp);
         else
   if(temp->data > key)
      temp = temp->lchild;
   else
      temp = temp->rchild;
        }
return(NULL);
}

/*an iterative function to print the binary tree in inorder*/
void inorder1(struct tnode *p)
{
  struct tnode *stack[100];
  int top;
  top = −1;
 if(p != NULL)
 {
    top++;
    stack[top] = p;
    p = p->lchild;
    while(top >= 0)
       {
          while ( p!= NULL)/* push the left child onto stack*/
           {
                       top++;
                 stack[top] =p;
                 p = p->lchild;
         }
         p = stack[top];
         top-;
         printf("%d\t",p->data);
         p = p->rchild;


         if ( p != NULL) /* push right child*/
           {
               top++;
                              stack[top] = p;
               p = p->lchild;
                 }

         }
    }
}
/* A function to insert a new node in binary search tree to
get a tree created*/
struct tnode *insert(struct tnode *p,int val)
{
   struct tnode *temp1,*temp2;
   if(p == NULL)
   {
      p = (struct tnode *) malloc(sizeof(struct tnode)); /* insert the new node as root node*/
      if(p == NULL)
        {
   printf("Cannot allocate\n");
   exit(0);
       }
    p->data = val;
    p->lchild=p->rchild=NULL;
   }
  else
  {
    temp1 = p;
   /* traverse the tree to get a pointer to that node whose child will be the newly created node*/
  while(temp1 != NULL)
  {
    temp2 = temp1;
    if( temp1 ->data > val)
         temp1 = temp1->lchild;
    else
         temp1 = temp1->rchild;
  }
  if( temp2->data > val)
  {
      temp2->lchild = (struct tnode*)malloc(sizeof(struct tnode));/ *inserts the newly created node
  as left child*/
     temp2 = temp2->lchild;
     if(temp2 == NULL)
          {
     printf("Cannot allocate\n");
     exit(0);
          }
    temp2->data = val;
    temp2->lchild=temp2->rchild = NULL;
  }
  else
  {
     temp2->rchild = (struct tnode*)malloc(sizeof(struct tnode));/ *inserts the newly created node
  as left child*/
     temp2 = temp2->rchild;
     if(temp2 == NULL)
          {
     printf("Cannot allocate\n");
     exit(0);
         }
     temp2->data = val;
     temp2->lchild=temp2->rchild = NULL;
  }
}
return(p);
}
void main()
{
   struct tnode *root = NULL, *temp = NULL;
   int n,x;
   printf("Enter the number of nodes in the tree\n");
   scanf("%d",&n);
   while( n - > 0)
       {
         printf("Enter the data value\n");
         scanf("%d",&x);
         root = insert(root,x);
       }
      printf("The created tree is :\n");
      inorder1(root);
      printf("\n Enter the value of the node to be searched\n");
      scanf("%d",&n);
      temp=search(root,n);
      if(temp != NULL)
          printf("The data value is present in the tree \n");
      else
          printf("The data value is not present in the tree \n");
}

Explanation

• Input: 1. The number of nodes that the tree to be created should have
  2. The data values of each node in the tree to be created
  3. The key value
• Output: If the key is present and appears in the created tree, then a message
  "The data value is present in the tree" appears. Otherwise the message
  "The data value is not present in the tree" appears.