Declaration rule in struct typedef

Question

I'm reading 'The C Programming Language' and encountered a problem about typedef of struct. The code is like this:

typedef struct tnode *Treeptr;
typedef struct tnode { /* the tree node: */
    char *word; /* points to the text */
    int count; /* number of occurrences */
    struct tnode *left; /* left child */
    struct tnode *right; /* right child */
} Treenode;

By the time we write

typedef struct tnode *Treeptr;

tnode is still not declared yet, but we don't get any compilation error, but when we change the statement above into:

typedef Treenode *Treeptr;

We get compilation error:

error: parse error before '*' token
warning: data definition has no type or storage class

What causes the difference? Isn't "struct tnode" the same as "Treenode"?

Answer 1

You can't use a type before it is defined.

With the typedef struct tnode { ... } Treenode; declaration, the type Treenode is not defined until the semi-colon is reached.

The situation with typedef struct tnode *Treeptr; is different. This tells the compiler 'there is a structure type called struct tnode, and the type Treeptr is an alias for a pointer to a struct tnode'. At the end of that declaration, struct tnode is an incomplete type. You can create pointers to incomplete types but you cannot create variables of the incomplete type (so you could define Treeptr ptr1; or struct tnode *ptr2; and they are the same type, but you could not define struct tnode node;).

The body of the struct tnode could be written as:

typedef struct tnode
{
    char    *word;
    int      count;
    Treeptr  left;
    Treeptr  right;
} Treenode;

because Treeptr is a known alias for the type struct tnode * before the structure is defined. You can't use Treenode *left; because Treenode is not a known alias until the final semi-colon is reached (roughly speaking).

Answer 2

When you declare TreePtr, you are not implementing the struct. That is known as a "forward declaration". Something like: "here we use this, but later I will explain it better". The implementation must appear later, only once, and that is what you find in the second typedef.

And TreePtr is not the same as the struct, because TreePtr will be in fact a new type that includes the fact of beeing a pointer.

Answer 3

A line typedef struct tnode *Treeptr; has implicit forward declaration of "tnode" struct. It's similar to:

typedef struct tnode Treenode;
typedef Treenode *Treeptr;

struct tnode { /* the tree node: */
    char *word; /* points to the text */
    int count; /* number of occurrences */
    struct tnode *left; /* left child */
    struct tnode *right; /* right child */
};