need help with search function

[ellenski]

Hi,

We were asked to make a Binary Search Tree program in C. It should be able to traverse the numbers (preorder, inorder, postorder) then display it. And locate the number and display it.

I have no probleming traversing and locating it. My problem is if the number isn't there when I locate it, I can't seem to make it display a message saying that the number cannot be found no matter where i put the code for displaying that error message. I have tried numerous ways but none have worked. Any suggestions would be appreciated. Here is my complete working code without the error message that will display if the number isn't there:

#include <stdlib.h>
#include <stdio.h>
#include <conio.h>

struct tree
{
   int data;
   struct tree *left;
   struct tree *right;
}*top,*a,*b;

struct tree *make(int m)
{
   struct tree *newnode;
   newnode=(struct tree *)malloc(sizeof(struct tree));
   newnode->data=m;
   newnode->right=newnode->left=NULL;
   return(newnode);
}

void left(struct tree *t,int x)
{
   if(t->left!=NULL)
      printf("\n Invalid!");
   else
      t->left=make(x);
}

void right(struct tree *t,int x)
{
   if(t->right!=NULL)
      printf("\n Invalid!");
   else
      t->right=make(x);
}

void inorder(struct tree *t)
{
   if(t!=NULL)
   {
      inorder(t->left);
      printf("\t %d",t->data);
      inorder(t->right);
   }
}

void preorder(struct tree *t)
{
   if(t!=NULL)
   {
      printf("\t %d",t->data);
      preorder(t->left);
      preorder(t->right);
   }
}

void postorder(struct tree *t)
{
   if(t!=NULL)
   {
      postorder(t->left);
      postorder(t->right);
      printf("\t %d",t->data);
   }
}

void locate(struct tree *t, int num)
{
   if ( t!=NULL )
   {
      do
      {
         locate(t->left,num);
         locate(t->right,num);
         if ( t->data==num )
            printf("\n\n The number is found.");
         break;
      } while (t->data!=num);
   }
}

void main()
{
   int num, choice, loc;
   char ans;
   clrscr();
   printf("\n Enter the root: ");
   scanf("%d",& num);
   top=make(num);
   a=top;
   do
   {
      printf("\n\n Add another number?(Y/N): ");
      scanf(" %c",&ans);
      if ( ans=='y' || ans=='Y' )
      {
         printf("\n Enter a number: ");
         scanf("%d",&num);
         if ( num==-1 )
            break;
         a=top;
         b=top;
         while ( num!=a->data && b!=NULL )
         {
            a=b;
            if ( num<a->data )
               b=a->left;
            else
               b=a->right;
         }
         if ( num<a->data )
         {
            printf("\n Left branch of %d is %d",a->data,num);
            left(a,num);
         }
         else
         {
            right(a,num);
            printf("\n Right Branch of %d is %d",a->data,num);
         }
      }
      else
      {
         do
         {
            clrscr();
            printf("\n MAIN MENU\n");
            printf("\n [1] Traverse");
            printf("\n [2] Locate");
            printf("\n [3] Exit");
            printf("\n\n Enter the number of your choice: ");
            scanf("%d",&choice);
            switch(choice)
            {
               case 1: clrscr();
                       printf("\n\nPreorder: ");
                       preorder(top);
                       printf("\n\nInorder: ");
                       inorder(top);
                       printf("\n\nPostorder: ");
                       postorder(top);
                       getch();
                       break;
               case 2: clrscr();
                       printf("\n\n Enter the number to locate: ");
                       scanf("%d",&num);
                       locate(top,num);
                       getch();
                       break;
               case 3: clrscr();
                       printf("\n Good Bye!");
                       getch();
                       exit(0);
               default: printf("\n\n Invalid Choice! Please try again.");
                        getch();
                        break;
            }
         } while ( choice!=3 );
      }
   } while ( ans=='y' || ans=='Y' );
   getch();
}

[kings_mitra]

As a simple solution you can try adding a flag for the purpose....
Add a global variable like :
int found = 0;
and update its value once member is found.

if(t->data == num)
{
    printf("\n\n The number is found.");
    found = 1;
}

and udate the Case 2 as:

case 2:
    printf("\n\n Enter the number to locate: ");
    scanf("%d",&num);
    locate(top,num);
    if (!found)
        printf("\n\n The number is not found.");
    found = 0;   //initialize it again for next run
    break;

[ellenski]

Thank you for the suggestion. =)