In C, what does "struct node{struct node *left;} mean?Is recursion possible even in structures?PLZ HELP!!?

Question

I have read about recursion in C functions where it's ok for a function to call itself inside it's own body.But what on earth the following code mean?

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

From the sytax I can see that inside the body of the structure "node" we are declaring two pointers "right" and "left" to the SAME structure. PLZ EXPLAIN WHAT'S GOING ON!!! Is this a valid syntax or it's an error in my book?If valid then what does it do?This whole concept is totally new to me and it's really frustrating that I am confused about something seemingly simple like this.So please spare a few minutes to explain this...

Mr Henni,Jonathan,OOPS,Husoski,Ratechetr,please answer if you are reading this....It will hardly take 2-3 minutes for Top Contributors like you!!

Answer 1

Two points here: a conceptual explanation and a syntax explanation. First, the concept....



The idea is that the structure contains some stuff (the "info" part, which can be as long or short as you'd like) and since this is a binary tree also two pointers to (usually) other such structures. The pointers are themselves just more of the data contained inside. Nothing special. You could, if you wanted, define a third such pointer... or more... or even less. (One less would mean something like a linked list.)



Just for grins, let me show you a similar structure but used for a doubly linked list:



struct node {

    int info;

    struct node *prev;

    struct node *next;

};



It's the same structure, really. But it does something COMPLETELY different.



How does the compiler know the difference? It doesn't. It has no idea. So far as the compiler is concerned, they are the exact same memory footprint and the variables have exactly the same semantic meaning, as well. There is no difference to the compiler. The difference comes ONLY in how YOU decide to use it.



In the binary tree case, your code will make certain that the 'left' and 'right' elements within each structure ONLY point to two OTHER structures (not itself, for example) and other code you write to traverse the binary tree will operate on the assumption that this is a tree structure. It's the code you write, in other words, which makes this a binary tree and not a doubly linked list.



By the way, it is possible to turn a binary tree into a directed acyclic graph (dag) by simply allowing the left or right pointers to point to structures that are also pointed at by other nodes, as well. In other words, there may be (but do not have to be) multiple paths from the root node to some other node. Again, this is just a matter of what YOU do with your structures. The compiler doesn't care, one way or the other.

...



Second point about syntax...



When you wanted a pointer to a structure, C allowed you to write that readily. But in this case, the structure isn't even declared yet. C is still reading the structure when it gets to the variables that need to point to the structure (not declared, quite yet.) C is able, though, to use the preceding "struct node" that started the structure when declaring variables within the structure. Which is nice. I think there was a time when it complained to me about this.



Suppose you needed two different structures that pointed to each other: struct A and struct B. How would you do that? Something like this:



struct B;

struct A {

    int info;

    struct B *left;

    struct B *right;

};

struct B {

    double otherinfo;

    struct A *left;

    struct A *right;

};



Note that you don't actually have to completely specify a struct before using it, if you are talking about pointers to one. Pointers can be completely specified without actually knowing what they point at, because the size is still knowable even if the specific elements with it aren't yet known. Once the above has been seen by the compiler, it then knows all it needs to know to proceed when it sees code using them.

Answer 2

Your interpretation is exactly correct. The structure contains two points to structures of the same type as itself.



This works because the structure is only holding pointers - and the structure size and shape (i.e. memory allocation) doesn't change depending on what the pointer points to. The "struct node *" declaration inside the structure simply tells the compiler that these pointers are intended to point to a struct node, so that it can scream and shout if you try to do something silly like point it at a string



(I guess you're looking at something like a binary tree?)

Answer 3

Eeyore and Pooh are suited of pals so i'm hoping they are consistently happy. it quite is probably achievable if there is not any honey left and Eeyore is going forward and shows some for Winnie the Pooh!