C recursive typedef struct

Question

#include <stdio.h>
#include <stdlib.h>

#define MAX_ELEMENT 100

typedef struct TreeNode{
    int weight;
    TreeNode *left_child;
    TreeNode *right_child;
} TreeNode;

typedef struct element{
    TreeNode *ptree;
    int key;
} element;

typedef struct HeapType{
    element heap[MAX_ELEMENT];
    int heap_size;
} HeapType;

and I get the errors:

error: unknown type name ‘TreeNode’
     TreeNode *left_child;
error: unknown type name ‘TreeNode’
     TreeNode *right_child;

I can't understand why...can you explain?

It should work fine if you change the declaration to `struct TreeNode *left_child;`. You can also add a preceding declaration: `typedef struct TreeNode`; followed by `struct TreeNode { TreeNode *left_child; ... }` — paulsm4, Nov 14 '19 at 06:18
The bottom line is the `typedef` for `TreeNode` is not complete when you use `TreeNode *left_child;`, etc.. You either include `struct` before `TreeNode *left_child;` or create a `typedef` using a *forward reference* for `struct TreeNode` — David C. Rankin, Nov 14 '19 at 06:20

Jonathan Leffler · Accepted Answer · 2019-11-14T06:48:25.530

With your code:

typedef struct TreeNode{
    int weight;
    TreeNode *left_child;
    TreeNode *right_child;
} TreeNode;

the name TreeNode is not known until the line } TreeNode; is parsed. When processing the line TreeNode *left_child;, the compiler knows that there is a type struct TreeNode, but it doesn't know anything about a type TreeNode.

You can also use:

typedef struct TreeNode Treenode;

struct TreeNode
{
    int weight;
    TreeNode *left_child;
    TreeNode *right_child;
};

The first line says "there is a a structure type struct TreeNode, and TreeNode is an alias for that type". The remaining lines of code define what it means to be a struct TreeNode.

Alternatively, as the other answers point out, you can use:

typedef struct TreeNode
{
    int weight;
    struct TreeNode *left_child;
    struct TreeNode *right_child;
} TreeNode;

The compiler knows enough about the type struct TreeNode to be able to handle pointers to the type as it reads the definition. Note C11 §6.7.2.1 Structure and union specifiers ¶3:

A structure or union shall not contain a member with incomplete or function type (hence, a structure shall not contain an instance of itself, but may contain a pointer to an instance of itself), …

Both robthebloke and Yoni Melki explained *WHY*the problem is occurring. Thank you for adding *BOTH* of the two possible solutions. — paulsm4, Nov 14 '19 at 06:22

score 3 · Answer 2 · edited Nov 14 '19 at 06:42

3

You need to write struct TreeNode* because the compiler still doesn’t know what is TreeNode (without the struct)

edited Nov 14 '19 at 06:42

Jonathan Leffler

730,956
141
904
1,278

answered Nov 14 '19 at 06:14

Yoni Melki

205
3
16

score 2 · Answer 3 · answered Nov 14 '19 at 06:14

2

The typedef doesn't kick in until after the struct definition, so you still need to use the struct keyword for the pointer decls.

typedef struct TreeNode{
    int weight;
    struct TreeNode *left_child;
    struct TreeNode *right_child;
} TreeNode;

answered Nov 14 '19 at 06:14

robthebloke

9,331
9
12

C recursive typedef struct

3 Answers3