BST Counting

This is a discussion on BST Counting within the C Programming forums, part of the General Programming Boards category; I'm trying to build up BST program in which a random number genarator is available too. So Random number generator ...

  1. #1
    Registered User
    Join Date
    Mar 2007
    Posts
    28

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

  2. #2
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,273
    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.

  3. #3
    Registered User
    Join Date
    Mar 2007
    Posts
    28
    Quote Originally Posted by brewbuck View Post

    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 : )

  4. #4
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,273
    Quote Originally Posted by m0ntana View Post
    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?

  5. #5
    Registered User
    Join Date
    Mar 2007
    Posts
    28
    Quote Originally Posted by brewbuck View Post
    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...

  6. #6
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,273
    Quote Originally Posted by m0ntana View Post
    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.

  7. #7
    Registered User
    Join Date
    Mar 2007
    Posts
    28
    Quote Originally Posted by brewbuck View Post
    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

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. BST array
    By Iron_Shortage in forum C Programming
    Replies: 5
    Last Post: 04-20-2009, 04:04 PM
  2. problem inserting into recursive BST
    By nfrandsen in forum C Programming
    Replies: 4
    Last Post: 09-13-2008, 08:03 PM
  3. counting nodes BST
    By qubit67 in forum C Programming
    Replies: 2
    Last Post: 05-01-2007, 08:46 AM
  4. I would love some input on my BST tree.
    By StevenGarcia in forum C++ Programming
    Replies: 4
    Last Post: 01-15-2007, 01:22 AM
  5. Splitting BST General
    By cpp_is_fun in forum C++ Programming
    Replies: 1
    Last Post: 11-25-2005, 02:02 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21