Binary Search Tree locate and display

[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();
}

[Greg8202]

Your locate recursive function does not look right. It could simply be:

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

[ellenski]

Thank you so much. Your suggestion really helped. =)