I'm trying to build up BST program in which a random number genarator is available too. So Random number generator will produces numbers according to user's choice and send them into the insertion function, then a tree will be created.
The point start here, after tree is created, I must count tree's single childs, the parent's that have one node only...
To do this, I made a investigation and I've come up such a idea that is, I'm gonna fill with -1 the non-available nodes, so -1 indicates that those parents have single child, the I will read all the tree into an temp array. Then I'll create such a algorithm that it returns number of single childs according to temp array.
So far, I've written a part of program but, I stuck on somewhere which is, How I'm gonna fill with -1 the nodes which are not available actually.
I mean
A is parent B is its first child and no second child is available, but I have to create second child that contains "-1"
A=0
B=8
C=-1
here is my code till now;
Code:
#include <stdio.h>
#include <stdlib.h>
typedef struct node{
int key;
struct node* left;
struct node* right;
}node;
int random ( int min, int max);
void insert( node** root, int key );
void list( node* root );
int main(){
node* searchtree=NULL;
node temparray[30];
int key;
int count;
int i=0;
printf("Enter The Count Value To Generate Random Numbers :\n");
scanf("%d",&count);
while(i!=count){
key=random(1,40);
printf("The Generated Random Key Is %d \n",key);
insert(&searchtree, key);
i++;
}
printf("Press Any Key To List All Items\n");
getch();
list(searchtree);
getch();
return 0;
}
int random(int min, int max){
return( (int) (min+(max-min+1) *(rand()/32768.0)) );
}
void insert( node** root, int key ){
int c;
int done = 0;
node* previous;
node* new = (node *)malloc(sizeof(node));
new->key = key;
new->left = NULL;
new->right = NULL;
if ( *root == NULL )
{
*root = new;
}
else
{
previous = *root;
do
{
if ( previous->key > new->key )
{
if ( previous->left == NULL )
{
previous->left = new;
done = 1;
}
else
{
previous = previous->left;
}
}
else if ( previous->key < new->key )
{
if ( previous->right == NULL )
{
previous->right = new;
done = 1;
}
else
{
previous = previous->right;
}
}
else
{
done = 1;
}
} while ( !done );
}
}
void list( node* root )
{
if( root != NULL )
{
list( root->left );
printf( "%d ", root->key );
list( root->right );
}
}