Thread: More binary tree probs

  1. #1
    Registered User
    Join Date
    Sep 2002
    Posts
    137

    More binary tree probs

    Hi again, still banging my head against a proverbial brick wall with these trees.
    Here's my code:
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    struct node {
    	char data;
       int count;
    	struct node *left;
    	struct node *right;
       };
    
    void insert_node (struct node *top,char x);
    
    
    int main () {
    
    	struct node n1,*ptr_n1;
       char bob = 'g';
       printf("Please enter a value :");
       scanf("%c",&n1.data);
       n1.left = NULL;
       n1.right = NULL;
       ptr_n1=&n1;
       insert_node (ptr_n1,bob);
       return 0;
    }
    
    void insert_node (struct node *top,char x) {
    	if (x < (*top).data)
       	insert_node ((*top).left,x);
       else insert_node ((*top).right,x);
    }
    When I run this it crashes my prompt. This program is an attempt to just join two nodes together before I code a loop that can constantly add new nodes correctly. Any ideas why it crashes?

    Another question is to do with searching my tree once its up and running. I have a character variable in each node. How do I search through the various nodes to find my char?
    Thanks
    http://uk.geocities.com/ca_chorltonkids

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,656
    The main problem with your code is that you only have one node. A tree is a dynamic structure, which means you need to create nodes at run-time (using malloc), and add these into the tree at the appropriate place.

    Have a look at this
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    struct node {
        char         data;
        struct node *left;
        struct node *right;
    };
    
    void insert_node ( struct node **root, char data ) {
        if ( *root == NULL ) {
            // a new leaf is needed
            struct node *newnode = malloc( sizeof( struct node ) );
            newnode->data = data;
            newnode->left = NULL;
            newnode->right= NULL;
            *root = newnode;
        } else {
            // decide which way to go
            if ( data < (*root)->data ) {
                insert_node( &(*root)->left, data );
            } else {
                insert_node( &(*root)->right, data );
            }
        }
    }
    
    void print_tree ( struct node *root ) {
        if ( root == NULL ) return;
        print_tree( root->left );
        printf( "%c", root->data );
        print_tree( root->right );
    }
    
    int main(void) {
        struct  node *tree = NULL;      // an empty tree
    
        // we pass a pointer to tree, so that it gets updated
        // when a node is allocated.
        // an alternative function call would be
        // tree = insert_node( tree, 'a' );
        // which would require some mods to the function
        // but would remove the ** in the function prototype
        // (if that's too confusing at the moment)
        insert_node ( &tree, 'c' );
        insert_node ( &tree, 'f' );
        insert_node ( &tree, 'b' );
        insert_node ( &tree, 'd' );
        insert_node ( &tree, 'a' );
        print_tree( tree );
        return 0;
    }

  3. #3
    Registered User
    Join Date
    Sep 2002
    Posts
    137
    Thanks, I think I've fixed the node creation problem with this code:
    Code:
    void insert_node (struct node *top,char x) {
       if ((top) == NULL)  {
        top = (node*) malloc (NODESIZE);
        (*top).data = x;
        (*top).left = NULL;
        (*top).right = NULL;
      }
    	else if (x < (*top).data)
       	insert_node ((*top).left,x);
       else insert_node ((*top).right,x);
    }
    Assuming this does produce the second node ( it compiles fine and runs without crashing so I assume it must. What must I do to retrieve the data from the second node?
    http://uk.geocities.com/ca_chorltonkids

  4. #4
    Registered User
    Join Date
    Sep 2002
    Posts
    137
    Thanks, I've sorted my problem now.
    http://uk.geocities.com/ca_chorltonkids

  5. #5
    End Of Line Hammer's Avatar
    Join Date
    Apr 2002
    Posts
    6,231
    Code:
    void insert_node (struct node *top,char x) {
       if ((top) == NULL)  {
        top = (node*) malloc (NODESIZE);
        (*top).data = x;
        (*top).left = NULL;
        (*top).right = NULL;
      }
       ...
    The problem here is that top is a pointer local to the function. If you assign anything to it, like the return from malloc() you would need to return top at the end.

    Unless, you do as Salem suggested, and pass the address of the pointer with this:
    >void insert_node (struct node **root,
    When all else fails, read the instructions.
    If you're posting code, use code tags: [code] /* insert code here */ [/code]

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 0
    Last Post: 11-04-2006, 11:07 AM
  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. Tutorial review
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 11
    Last Post: 03-22-2004, 09:40 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM