Thread: searching and insertion in a binary search tree

  1. #1
    Registered User
    Join Date
    Sep 2004
    Posts
    63

    Unhappy searching and insertion in a binary search tree

    i have written the code for searching and insertion in a binary search tree...i understood most of the things in that but there are some doubts which i would be very grateful if u could make me understand about them....
    Code:
    #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 ( "" );
      } else {
        pretty_print ( tree->right, level + 1 );
        printf ( "%d", 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 );
    printf("the tree is");
      pretty_print ( tree, 0 );
      printf ( "\n the tree in inorder traversal is:\n");
      inorder_print ( tree );
      for ( i = 0; i < 100; i++ ) {
        if ( search ( tree, i ) != 0 ) {
          printf ( "%-4d", i );
            printf ( "\n%d numbers found", n );
          ++n;
        }
      }
    
       getchar();
    
      return 0;
    }
    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 but i have some doubts,i hope you would help me out,which are as follows:
    --now why is it taking the random numbers by itself and taking from th user,is it becoz of the ran()%100 function?what is it doing over there?i want to take inputs from the user,how will i do that?
    --also i could not understand the logic on how to take the inorder traversal while running the program,although i know how does it work that is by first taking left child ,the root and then the right child....but could u plz help me out in finding which is my right child ,root and left child while running the program?
    --how would i know that the number is not found?what would i write in the above program for that?
    --and in our main() function the second time we are using our foor loop could u plz tell me why have we taken i<100 over there?why are wetaking it till 100?
    i would be really grateful if u can make me understand about those doubts.

  2. #2
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    >i have written the code for searching and insertion in a binary search tree
    You may want to reword this statement. Aside from
    Code:
    printf("the tree is");
    and
    Code:
    printf ( "\n the tree in inorder traversal is:\n");
    All of that code is mine. Palming off another's code as your own is generally frowned on.

    >i hope you would help me out
    No, because as I told you on Daniweb, you've shown no improvement in several months despite being helped by some brilliant people. Clearly you aren't interested in getting better, and your threads are nothing but a time sink for us.
    My best code is written with the delete key.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Binary Tree, couple questions
    By scoobasean in forum C Programming
    Replies: 3
    Last Post: 03-12-2005, 09:09 PM
  2. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  3. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM