Binary Search Tree in C

Sort integers using binary search tree

Page 1 of 1

11 Replies - 5466 Views - Last Post: 27 September 2010 - 09:52 AM Rate Topic: -----

#1 need_helpp  Icon User is offline

  • D.I.C Head

Reputation: -2
  • View blog
  • Posts: 72
  • Joined: 08-September 09

Binary Search Tree in C

Posted 26 September 2010 - 10:57 PM

I wrote a program which should add integers to the binary tree, sort them and check if the number is in the tree... My program is pretty much done. Only thing I need to do is get out of the case a: and display main menu and go back to the switch statement...
Thanks


Here is my code:
#include <stdlib.h>
#include <stdio.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 locate(struct tree *t, int num)
{
   if ( t==NULL )
   { 
      printf("\n The number is NOT found!");
      

   }
   else
   {
      if ( t->data==num )
       {     printf("\n --------------------------");
         printf("\n The number is found\n");
          printf("\n --------------------------");
}
      else if ( t->data<num )
         locate(t->right,num);
      else
         locate(t->left,num);	 
   }
}



int main(void)
{
   int num, loc;
   char ans;
   char choice;

   printf("\na. Add an integer to the tree\n");
   printf("b. List the sorted list of the integers in the tree\n");
   printf("c. Find if an integer exists in the tree\n");
   printf("d. Exit\n");
   scanf("%s", &choice);
   
switch(choice)
{  case'a':
    printf("\n Enter a number: ");
    scanf("%d",& num);
    top=make(num);
    a=top;
   do
   {
      printf("\n\n Add a 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 )
	 {
	     left(a,num);
	 }
	 else
	 {
	    right(a,num);
	 }
      }
      else
      {
      //How do I get out from here and go thru the switch again???
      }
     } while ( ans=='y' || ans=='Y' );
      scanf("%s",&choice);
	
	       case 'b':
		       printf("\n\nSorted Tree:\n   ");
		       inorder(top);
		       break;
	       case 'c':
		       printf("\n\n Enter the number to locate: ");
		       scanf("%d",&num);
		       locate(top,num);
		       break;
              case 'd': exit(0);
		      break;	

	    }
}





Is This A Good Question/Topic? 0
  • +

Replies To: Binary Search Tree in C

#2 janotte  Icon User is offline

  • code > sword
  • member icon

Reputation: 990
  • View blog
  • Posts: 5,141
  • Joined: 28-September 06

Re: Binary Search Tree in C

Posted 26 September 2010 - 11:14 PM

Did you have a question?
Was This Post Helpful? 0
  • +
  • -

#3 need_helpp  Icon User is offline

  • D.I.C Head

Reputation: -2
  • View blog
  • Posts: 72
  • Joined: 08-September 09

Re: Binary Search Tree in C

Posted 26 September 2010 - 11:27 PM

My question is:

For case a: inside of do while loop, if user enters anything other than y or Y , I need to get out of that loop. That's where I am having problem. I comment it on the code where I need help at the end of case a.

Thanks
Was This Post Helpful? 0
  • +
  • -

#4 janotte  Icon User is offline

  • code > sword
  • member icon

Reputation: 990
  • View blog
  • Posts: 5,141
  • Joined: 28-September 06

Re: Binary Search Tree in C

Posted 26 September 2010 - 11:38 PM

Your code is so poorly laid out it is too hard for me to work out what is happening where.

Good code layout makes it far easier to write correct code.

A good cook has a clean and well organised kitchen. You need to have a clean and well organised code layout if you are going to see easily what you have written and where you have made a mistake.

So choose one of the common indentation styles and use it consistently.
http://en.wikipedia....ki/Indent_style

Go through your code and lay it out so the braces match and the indentation tells you and us what the scope of various parts of the code are.

Once you have done that repost your code.
Was This Post Helpful? 0
  • +
  • -

#5 aaa111  Icon User is offline

  • D.I.C Regular

Reputation: 88
  • View blog
  • Posts: 284
  • Joined: 21-February 07

Re: Binary Search Tree in C

Posted 26 September 2010 - 11:44 PM

I have modified the code for what you wanted:
#include <stdlib.h>
#include <stdio.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 locate(struct tree *t, int num)
{
   if ( t==NULL )
      printf("\n The number is NOT found!");
      
  else
	{
      if ( t->data==num )
       {
		printf("\n --------------------------");
         printf("\n The number is found\n");
          printf("\n --------------------------");
	}
      else if ( t->data<num )
         locate(t->right,num);
      else
         locate(t->left,num);	 
   }
}



int main(void)
{
   int num, loc;
   char ans;
   char choice;
 
   do
   {
   printf("\na. Add an integer to the tree\n");
   printf("b. List the sorted list of the integers in the tree\n");
   printf("c. Find if an integer exists in the tree\n");
   printf("d. Exit\n");
   scanf("%s", &choice);


    switch(choice)
	{
    case'a':
	printf("\n Enter a number: ");
    scanf("%d",& num);
    top=make(num);
    a=top;
    do
    {
      printf("\n\n Add a 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 )
		{
	     left(a,num);
		}
		else
		{
	    right(a,num);
		}
      }
    else
      {
      break;//How do I get out from here and go thru the switch again???
      }
     } while ( ans=='y' || ans=='Y' );
     
	case 'b':
		       printf("\n\nSorted Tree:\n   ");
		       inorder(top);
		       break;
	case 'c':
		       printf("\n\n Enter the number to locate: ");
		       scanf("%d",&num);
		       locate(top,num);
		       break;
    case 'd': exit(0);
		      break;	

	}
   }   while(choice>='a'&&choice<='d');

}



Find yourself what i changed.Also as janotte said your code are poorly laid out.Follow his post.

This post has been edited by aaa111: 26 September 2010 - 11:48 PM

Was This Post Helpful? -1
  • +
  • -

#6 need_helpp  Icon User is offline

  • D.I.C Head

Reputation: -2
  • View blog
  • Posts: 72
  • Joined: 08-September 09

Re: Binary Search Tree in C

Posted 27 September 2010 - 06:34 AM

Thanks for your reply. I tried the changes that you suggested and
after I enter "n" for the question "Add a number?" it just stops and do nothing.

It doesn't go back to the top of the switch statement.How can I fix that?
Was This Post Helpful? 0
  • +
  • -

#7 janotte  Icon User is offline

  • code > sword
  • member icon

Reputation: 990
  • View blog
  • Posts: 5,141
  • Joined: 28-September 06

Re: Binary Search Tree in C

Posted 27 September 2010 - 06:48 AM

Please show us your code as it is now.

This post has been edited by janotte: 27 September 2010 - 06:49 AM

Was This Post Helpful? 0
  • +
  • -

#8 JackOfAllTrades  Icon User is offline

  • Saucy!
  • member icon

Reputation: 6075
  • View blog
  • Posts: 23,543
  • Joined: 23-August 08

Re: Binary Search Tree in C

Posted 27 September 2010 - 06:50 AM

This
scanf("%s", &choice);

is wrong. Choice is a char, and you're reading it as if it were a string.
Was This Post Helpful? 0
  • +
  • -

#9 need_helpp  Icon User is offline

  • D.I.C Head

Reputation: -2
  • View blog
  • Posts: 72
  • Joined: 08-September 09

Re: Binary Search Tree in C

Posted 27 September 2010 - 06:53 AM

View Postjanotte, on 27 September 2010 - 05:48 AM, said:

Please show us your code as it is now.


The code is exactly the one "aaa111" posted. which has another do while loop inside of the main.
Was This Post Helpful? 0
  • +
  • -

#10 aaa111  Icon User is offline

  • D.I.C Regular

Reputation: 88
  • View blog
  • Posts: 284
  • Joined: 21-February 07

Re: Binary Search Tree in C

Posted 27 September 2010 - 07:25 AM

View Postneed_helpp, on 27 September 2010 - 05:34 AM, said:

Thanks for your reply. I tried the changes that you suggested and
after I enter "n" for the question "Add a number?" it just stops and do nothing.

It doesn't go back to the top of the switch statement.How can I fix that?

That is one of a common problem of scanf,when you input with the first scanf a newline is left behind in the input stream,unconsumed.So,one of the way to fix this is to use something like this:
scanf("\n%c",&ans);

This will consume the newline from the buffer or you could do this:
scanf(" %c",&ans);//extra space

You have to this for all the scanf.This is one of the cheap solution,there are other but i am sort in time now.

This post has been edited by aaa111: 27 September 2010 - 07:26 AM

Was This Post Helpful? 1
  • +
  • -

#11 JackOfAllTrades  Icon User is offline

  • Saucy!
  • member icon

Reputation: 6075
  • View blog
  • Posts: 23,543
  • Joined: 23-August 08

Re: Binary Search Tree in C

Posted 27 September 2010 - 09:25 AM

I created a blog entry on this just the other day.
Was This Post Helpful? 0
  • +
  • -

#12 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon

Reputation: 5881
  • View blog
  • Posts: 12,758
  • Joined: 16-October 07

Re: Binary Search Tree in C

Posted 27 September 2010 - 09:52 AM

Try to keep your main short. Also, try to keep the switch short. If it's too complicated to easily follow, move the code out into other functions.

e.g.
char showMenu() {
	char choice;

	printf("\na. Add an integer to the tree\n");
	printf("b. List the sorted list of the integers in the tree\n");
	printf("c. Find if an integer exists in the tree\n");
	printf("d. Exit\n");
	scanf("%c", &choice); // your bug, fixed
	return choice;
}

int main(void) {
	int keepGoing = 1;
	while(keepGoing) {
		char choice = showMenu();
		switch(choice) {
			case 'a': 
				addValue(); 
				break;
			case 'b':
				printf("\n\nSorted Tree:\n   ");
				inorder(top);
				break;
			case 'c':
				findValue();
				break;
			case 'd': 
				keepGoing = 0;
				break;
			default:
				printf("\n\nUnknown option: %c\n", choice);
		}
	}
}


Was This Post Helpful? 0
  • +
  • -

Page 1 of 1