Declaring a binary tree in C

Question

In c++ its something like this:

struct node{
   int value;
   node *left;
   node *right;
};

and in function, when i need it, il use it like this:

node *r;
r = new node();
r -> inf = 1;
r -> left = r -> right = null;

but how is this working in C ? i tryed:

struct node{
    int value;
    node *left;
    node *right;
};

but i got error: indentifier node is undefined, so i changed in:

struct node{
    int value;
    struct node *left;
    struct node *right;
};

but now, if i try to make a new variable:

node *r;

i get error: identifier node is undefiner at *r declaration line, What am I doing wrong?

possible duplicate of [typedef struct vs struct definitions](http://stackoverflow.com/questions/1675351/typedef-struct-vs-struct-definitions) — ugoren, Oct 31 '13 at 20:30
Doing wrong? Learning C++ before C, maybe? Have fun malloc-ing the new nodes, will be waiting for that one :) ... just to prevent another duplicate http://stackoverflow.com/a/4085018/1162141 — technosaurus, Oct 31 '13 at 21:06

Zach · Answer 1 · 2013-10-31T21:54:54.103

2

In C (as opposed to C++) you still need to use the struct keyword everywhere (or use a typedef). Try this:

struct node *r;

or this:

typedef struct node {
    int value;
    struct node *left;
    struct node *right;
} node;

As mentioned in a comment, the node references from inside the struct still need the struct keyword, since the typedef does not yet exist. But now you can use node without the struct keyword.

edited Oct 31 '13 at 21:54

answered Oct 31 '13 at 20:27

Zach

7,730
3
21
26

+1. Would also be worth mentioning that `new node()` isn't valid C. – simonc Oct 31 '13 at 20:30
2

I think you still need to explicitly specify `struct node` inside the structure declaration for the children pointers. – Rerito Oct 31 '13 at 20:30
You're right, you do still need the struct keyword there. I will edit my answer. – Zach Oct 31 '13 at 21:53

Rerito · Answer 2 · 2013-10-31T20:45:22.463

As I stated in my comment, you cannot use a typedef within the structure being typedefed like suggested by Zach. You need to explicitly name the structure in use :

struct node {
    int value;
    struct node *left;
    struct node *right;
}

Moreover, I would recommend not to use a typedef unless you need to opacify a data type. Typedefing things just for the sake of writing less characters is not a good practice.

Still, if you are really really lazy, the typedef has to be done before the struct declaration, as in the example below :

/* Note that you can't use the same name for the struct and the typedef */
typedef struct node Node;
struct node {
    int value;
    Node *left;
    Node *right;
};

Then, if you are trying to implement binary trees, you are likely to implement the related methods. You will surely need a reference to the parent of a node to make insertion and deletion easier. Keep it in mind !

score 0 · Accepted Answer · answered Oct 31 '13 at 20:40

Anytime you refer to your struct you must refer to it as:

struct node * r;

So your struct definition should look like this:

struct node {
    int value;
    struct node * left;
    struct node * right;
}

Also, the new keyword is not in ANSI C. Since you are working with a pointer, you need to allocate the memory using malloc(). So

struct node * r = malloc(sizeof(struct node));
r->value = 0;
r->left = NULL;
r->right = NULL;

would allocate memory and initialize the records inside.

If you do not want to refer to it as struct node as the type, you can use a typedef:

typedef struct node {
    int value;
    struct node * left;
    struct node * right;
} node;

Though you still need to refer the pointers inside the record as struct node since it is declared within the typedef. Now you can reference as:

node * r = malloc(sizeof(node));

@simonc You do not de-reference a struct, only variables. `sizeof(node)` is the number of bytes of the record. `sizeof(node*)` is the number of bytes for the pointer. But `sizeof(*node)` is a compilation error. — ShooShoSha, Oct 31 '13 at 21:07

Declaring a binary tree in C

3 Answers3