building a tree

This is a discussion on building a tree within the C Programming forums, part of the General Programming Boards category; Hi, I'm trying to make a predictive text program, so I'm going to build a tree with pointers. Every node ...

  1. #1
    Registered User
    Join Date
    Jan 2006
    Posts
    3

    building a tree

    Hi,
    I'm trying to make a predictive text program, so I'm going to build a tree with pointers. Every node must have 9 branches since the input from the user is through the numeric keypad (like the T9).
    I have found some codes to build trees but they're usually for binary trees. How do I define that I want 9 branches coming out of every node (instead of a left and right)?

    Code:
    typedef struct node
    { 
    
    int number;
    struct node *left;
    struct node *right;
    
    };

  2. #2
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,484
    struct node *branches[9];

  3. #3
    Registered User
    Join Date
    Jan 2006
    Posts
    3
    I have changed the code like you said, I'm trying it with 3 branches at the moment. I'm trying to build 3 branches coming out of the root node, 1st branch having a value of 2, 2nd branch having a value of 3 and the 3rd having a value of 4. My code won't compile can you please tell me what's wrong?
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    typedef struct node
    { 
    #define BRANCHES    3
    struct node*     branch[ BRANCHES ];
    }node;
    
    struct node *root = 0;
    
    main(struct node **leaf)
    { 
    
    			if( *leaf == 0 )
    		{
    			*leaf = malloc( sizeof( struct node ) );
    		
    			 
    			leaf->branch[1] = 2;
    			leaf->branch[2] = 3;
    			leaf->branch[3] = 4;
    			
    		}
    		
    		
    	return 0;
    }

  4. #4
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,484
    > main(struct node **leaf)
    New and interesting ways of declaring main()
    Try one of the normal forms.

    > leaf->branch[1]
    Arrays start at 0, not 1

    If you'd figured out how to allocate *left and *right pointers, then there really isn't anything more difficult than that.

    > branches[ BRANCHES ] rather than branch[ BRANCHES ]. What do you guys feel is right?
    I often use the plural form when declaring arrays of things, if that makes the code more readable.

    As for putting the #define inside the struct, I wouldn't do that. It seems to imply a scope which simply isn't there.

  5. #5
    Registered User
    Join Date
    Jan 2006
    Posts
    3
    This still doesn't compile, there's something wrong with the lines:
    I consider myself a beginner in C i'm sorry if it's a very silly question.

    *leaf->branches[0]->value = 2;
    *leaf->branches[1]->value = 3;
    *leaf->branches[2]->value = 4;

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #define BRANCHES    3
    
    typedef struct node
    { 
    struct node *branches[ BRANCHES ];
    struct node *value;
    };
    
    
    
    void main()
    { struct node *root = 0;
    struct node **leaf;
    		
    		
    		if( *leaf == 0 )
    		{
    			*leaf = malloc( sizeof( struct node ) );
    			 
    			*leaf->branches[0]->value = 2;
    			*leaf->branches[1]->value = 3;
    			*leaf->branches[2]->value = 4;
    		}
    		
    }

  6. #6
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,484
    See, that's where it all falls apart.
    I thought you actually knew something about what you were trying to do.

  7. #7
    ex-DECcie
    Join Date
    Dec 2005
    Posts
    125
    There's at least a few things that my compiler gakked on....

    My comments are in red in the code block below.... Just a
    couple of pointers (no pun intended) to get you going in the
    right direction.....


    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #define BRANCHES    3
    
    typedef struct node
    { 
    struct node *branches[ BRANCHES ];
    struct node *value;
    };      /* My compiler says: "
              useless keyword or type name in empty
              declaration."   I think you forgot "node" here
             between the closing brace and semilcolon */
    
    
    
    void main()
    { struct node *root = 0;
    struct node **leaf;
    		
    		
    		if( *leaf == 0 )
    		{
    			*leaf = malloc( sizeof( struct node ) );
    
    /* You've got some precedence issues.  For starters, it should be
     (*leaf)->branches[0]->value
    But, even with that, it still won't compile.   You've declared 
    value as a pointer to struct node, and you're trying to set it to an
    integer value here.
    My compiler says: 
    assignment makes integer from pointer without a cast
    And THAT will usually cause a seg fault when it is run.
    I'm not sure if you want value to be an int or not, but it
    does not seem that you'd want it to be a pointer to another 
    struct node.
    */			 
    			*leaf->branches[0]->value = 2;
    			*leaf->branches[1]->value = 3;
    			*leaf->branches[2]->value = 4;
    		}
    		
    }
    [/QUOTE]

  8. #8
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,484
    Selent, here's a bit of code to show you some ideas of what to do.
    But you should really study a bit more C, and how binary trees work in particular before trying this for real.

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    #define BRANCHES    9
    typedef struct node
    {
      struct node *branches[ BRANCHES ];
      int          value;
    } node ;
    
    node *makeNode ( int value ) {
      node *result = malloc ( sizeof *result );
      if ( result != NULL ) {
        int i;
        for ( i = 0 ; i < BRANCHES ; i++ ) {
          result->branches[i] = NULL;
        }
        result->value = value;
      }
      return result;
    }
    
    node *addTree ( node *tree, int value, int branchNum ) {
      node *newNode = makeNode ( value );
      if ( tree == NULL ) {
        return newNode;
      } else {
        tree->branches[branchNum] = newNode;
        return tree;
      }
    }
    
    int main ( ) {
      node *tree = NULL;
      tree = addTree ( tree, 0, 0 );
      tree = addTree ( tree, 1, 1 );
      tree = addTree ( tree, 2, 2 );
      return 0;
    }
    Everyone else who wants to chew the fat over preprocessor and naming semantics should play here
    building a tree - The Off Topic Babble

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Binary Tree Search
    By C++Newbie in forum C++ Programming
    Replies: 7
    Last Post: 04-05-2011, 01:17 AM
  2. Interpreter.c
    By moussa in forum C Programming
    Replies: 4
    Last Post: 05-28-2008, 05:59 PM
  3. 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
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM

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