Thread: BST Counting

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 );
  }
}

Seems like a very strange approach. Why not take advantage of the tree structure to simplify things?

1. The number of leaf nodes in a tree is equal to the number of leaves on its left side, plus the number of leaves on its right side.
2. If a tree has no left or right side, it has 1 leaf.

That is all you need.

Originally Posted by brewbuck

1. The number of leaf nodes in a tree is equal to the number of leaves on its left side, plus the number of leaves on its right side.
2. If a tree has no left or right side, it has 1 leaf.

That is all you need.

First of all thanks for answer,

Actuallay, I'm very newbie on this BST data topic, but I've been learning...What I didn't understand from what you wrote is that, how come a random generated tree's right side and left side equals each other.

Anyway, I'll be working on it, if any helps or suggestion, it'd be nice of course : )

Originally Posted by m0ntana

Actuallay, I'm very newbie on this BST data topic, but I've been learning...What I didn't understand from what you wrote is that, how come a random generated tree's right side and left side equals each other.

What do you mean by "equal?" Equal in size? What makes you think that would be the case?

Originally Posted by brewbuck

What do you mean by "equal?" Equal in size? What makes you think that would be the case?

Yes I mean equal in size, if left side contains 60 nodes, right sides contains 60 too, if I didnt misunderstood from your answer...

Originally Posted by m0ntana

Yes I mean equal in size, if left side contains 60 nodes, right sides contains 60 too, if I didnt misunderstood from your answer...

That isn't what I said at all. I said that the number of leaves in a tree is equal to the number of leaves on the left side plus the number of leaves on the right side. Nothing in there says the number on the left has to be equal to the number on the right.

Originally Posted by brewbuck

That isn't what I said at all. I said that the number of leaves in a tree is equal to the number of leaves on the left side plus the number of leaves on the right side. Nothing in there says the number on the left has to be equal to the number on the right.

ok then i misunderstood, by the way I've almost completed the program