searching and inserting node in a binary search tree

[galmca]

hi...i am really facing a problem in printing a "binary search tree which does an inorder traversal and searches for a node and insert a node"....so i have written a program for that but it doesn't print a binary search tree and is giving some strange grabage values i don't know why?so i would be really greateful if u guys can take a look at my program and can let me know what am i doing wrong?and can bring about necessary changes or modifications in my program.

#include<stdio.h>
#include<conio.h>
struct node
{
int data;
struct node *left,*right;
};
typedef struct node tree;
void create( tree **p,int d)
{
  if(*p==NULL)
   {
    *p=(tree*)malloc(sizeof(tree));
    (*p)->data=d;
    (*p)->left=NULL;
    (*p)->right=NULL;
  }
   else
  {
    if(d<(*p)->data)
  {
  create(&((*p)->left),d);
 }
else
  {
   create(&((*p)->right),d);
   }
 }
}
void output(tree *p,int level)
{
int i;
if(p)
 {
 output(p->left,level+1);
 printf("\n");
 for(i=0;i<level;i++)
 printf(" ");
 printf("%d",p->data);
 output(p->right,level+1);
 }
}
  int search(tree *p,int data)
 {
 int flag=0;
  while(p!=NULL)
     {
     if(p->data==data)
       {
       flag=1;
       return(flag);
       }
       else
       if(data<p->data)
       {
       p=p->left;
       }
       else
       {
       p=p->right;
       }
     }
   return (flag);
 }
 void main()
 {
 tree *first=NULL;
  int flag;
 int number=0;
 char ch;int d;
 int data;
 clrscr();
  printf("\ninput choice 'b' to break:");
 ch=getchar();
 while(ch!='b')
 {
 fflush(stdin);
 printf("input information of the node:");
 scanf("%d",&data);
 fflush(stdin);
 printf("\ninput choice 'b' to break:");
 ch=getchar();
 }
 number--;
 printf("number of elements in the list is %d",number+1);
create(&first,d);
 printf("tree is:\n");
 output(first,1);
 fflush(stdin);
 printf("input the information of the node which we want to search:");
 scanf("%d",&data);
 flag=search(first,data);
 if(flag)
 {
 printf("search is successful");
 }
 else
 {
 printf("search is unsuccessful");
 }
 getch();
 }

please help me out!!!!!!!!

[Narue]

>*p=(tree*)malloc(sizeof(tree));
If you really are using C then there's no good reason to cast malloc. It hides the fact that you forgot to include stdlib.h.

>void main()
main doesn't return void, it never has. It returns int, and nothing else.

>fflush(stdin);
fflush is only defined for output streams, using it with an input stream is wrong.

Here is a much cleaner way to write a binary search tree:

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

struct node {
  int data;
  struct node *left;
  struct node *right;
};

int search ( struct node *tree, int key )
{
  if ( tree == NULL ) {
    return 0;
  } else if ( key == tree->data ) {
    return 1;
  } else if ( key < tree->data ) {
    return search ( tree->left, key );
  } else {
    return search ( tree->right, key );
  }
}

struct node *insert ( struct node *tree, int key )
{
  if ( tree == NULL ) {
    tree = malloc ( sizeof *tree );
    if ( tree == NULL )
      return tree;

    tree->data = key;
    tree->left = tree->right = NULL;
  } else if ( key < tree->data ) {
    tree->left = insert ( tree->left, key );
  } else {
    tree->right = insert ( tree->right, key );
  }

  return tree;
}

void pretty_print ( struct node *tree, int level )
{
  if ( tree == NULL ) {
    printf ( "%*s~\n", level * 3, "" );
  } else {
    pretty_print ( tree->right, level + 1 );
    printf ( "%*s%d\n", level * 3, "", tree->data );
    pretty_print ( tree->left, level + 1 );
  }
}

void inorder_print ( struct node *tree )
{
  if ( tree == NULL )
    return;

  inorder_print ( tree->left );
  printf ( "%-4d", tree->data );
  inorder_print ( tree->right );
}

int main ( void )
{
  struct node *tree = NULL;
  int i, n = 0;

  for ( i = 0; i < 10; i++ )
    tree = insert ( tree, rand() % 100 );

  pretty_print ( tree, 0 );
  printf ( "\n---------------------------\n" );

  inorder_print ( tree );
  printf ( "\n---------------------------\n" );

  for ( i = 0; i < 100; i++ ) {
    if ( search ( tree, i ) != 0 ) {
      printf ( "%-4d", i );
      ++n;
    }
  }

  printf ( "\n%d numbers found", n );
  printf ( "\n---------------------------\n" );

  getchar();

  return 0;
}

[galmca]

OUTPUT SHOWING ON RUNNING THE PROGRAM:
the tree is:
95908256484630261715
the tree in inorder traversal is:
1517263046485682909515
0 numbers found17
1 numbers found26
2 numbers found30
3 numbers found46
4 numbers found48
5 numbers found56
6 numbers found82
7 numbers found90
8 numbers found95
9 numbers found
__________________

I TRIED TO WRITE THE ABOVE CODE AS YOU MENTIONED,SO THANKS ALOT FOR THAT BUT I HAVE SOME DOUBTS ABOUT THIS PROGRAM,I HOPE YOU WOULD HELP ME OUT HERE,THESE ARE AS FOLLOWING:

--NOW WHY IS IT TAKING THE RANDOM NUMBERS BY ITSELF AND IS NOT TAKING ANY INPUT FROM THE USER,IS IT BECOZ OF THE ran()%100 function,WHAT IS IT DOING OVER THERE?I WANT TO TAKE THE INPUTS FROM THE USER.
--ALSO,I COULD NOT UNDERSTAND THE LOGIC ON HOW TO TRAVERSE THE INORDER,I KNOW THAT IN INORDER WE FIRST PERFORM THE LEFT CHILD THEN THE ROOT AND THEN THE RIGHT CHILD.I KNOW THAT BUT COULD YOU PLEASE HELP ME UNDERSTAND ON HOW WOULD I DECIDE THAT WHICH NUMBER WILL BE MY ROOT AND WHICH ARE GOING TO BE MY LEFT AND RIGHT CHILD WHILE RUNNING THE PROGRAM.
--HOW WOULD I KNOW THAT IF THE NUMBER IS NOT FOUND,THEN WHAT WOULD I WRITE IN THE ABOVE PROGRAM,TO SHOW THAT.
--AND,IN OUR main() FUNCTION,THE SECOND TIME WE ARE USING FOR LOOP ,CAN YOU PLEASE TELL ME WHY HAVE WE TAKEN i<100 OVER THERE?WHY ARE WE TAKING IT TILL 100?

I WOULD BE REALLY GRATEFUL IF YOU CAN MAKE ME UNDERSTAND ABOUT THOSE DOUBTS.

[Acidburn]

do you normally shout?

[Narue]

>I WOULD BE REALLY GRATEFUL IF YOU CAN MAKE ME UNDERSTAND ABOUT THOSE DOUBTS.
I've come to the conclusion that you're beyond any help. I've seen you posting on several forums known for high quality help for months, yet you've learned NOTHING. Your code is still riddled with undefined behavior, incorrect constructs, and general poor planning. Now, what's to make me believe that the time I spend answering your questions will not be completely wasted?

I come here to help people who want to improve, not watch what I say be ignored. I refuse to help you any more until you can show that you've actually paid attention to the kind and knowledgeable people who have apparently wasted their time with you.

[Fasola]

>I WOULD BE REALLY GRATEFUL IF YOU CAN MAKE ME UNDERSTAND ABOUT THOSE DOUBTS. I've come to the conclusion that you're beyond any help. I've seen you posting on several forums known for high quality help for months, yet you've learned NOTHING. Your code is still riddled with undefined behavior, incorrect constructs, and general poor planning. Now,....

LOL@^^^

play nice Narue