-
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;
};
-
struct node *branches[9];
-
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;
}
-
> 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.
-
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;
}
}
-
See, that's where it all falls apart.
I thought you actually knew something about what you were trying to do.
-
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]
-
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
http://cboard.cprogramming.com/showthread.php?t=74051