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.