tree data structure in C

Question

0.00/5 (No votes)

See more:

Hello forum,

is it possible to create a tree data structure in pure C?
This is not about a binary tree but every node shall have 0-n children.

The tree shall never be changed at runtime. Since this is for an embedded (Microchip Pic32) project, RAM is an issue. So I'd like to store the whole thing in code memory. Usually that's given for everything "const".

This is what I tried:

C

/* Header */
typedef struct TreeNode TreeNode;

/* Source */
struct TreeNode{
    int id;
    char* text;
    TreeNode* children[]; // List of child nodes
};

void DoSth(void)
{
    static const TreeNode tree = {
        0, "hidden", (TreeNode[3]){
            (TreeNode){1, "child", NULL},           // (1)
            (TreeNode){2, "secondChild", NULL},     // (1)
            (TreeNode){3, "thirdChild", NULL}       // (1)
	}
    };                                              // (2)

    // Code that's actually using the data
}

I know for sure that within the struct definition, children has to be referred to by pointers since TreeNode itself is not fully defined at that time.

But Compiler complains (numbering by me)

(1) non-static initialization of a flexible array member
(2) initializer element is not constant

(1) How should that not be static? Everything is given for the initialization.

(2) Same question as (1). Why is that not constant? And this is especially important given the embedded low RAM environment.

Posted 5-May-15 22:40pm

lukeer

Updated 5-May-15 22:46pm

v2

Add a Solution

2 solutions

Add a Solution

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Richard MacCutchan · Answer 1 · 2015-05-05T22:59:00

Solution 1

You are trying to mix static and dynamic data, so the compiler does not know how much space to reserve. You probably need a different structure for child nodes that do not themselves have children. You cannot declare an array as NULL as you have tried to do in your child nodes.

Posted 5-May-15 22:59pm

Richard MacCutchan

Comments

lukeer 7-May-15 2:06am

Ok, so let's for now forget the static data part.
A pointer to an array of child nodes should be possible. How to initialize that?

And then back to the reason for the static part. How to keep the completely initialized data off RAM and store it in flash? Is it even possible to store pointer stuff in flash?

[no name] 7-May-15 4:03am

Yes it is all possible, but in order to create the information at compile time you must use fixed sizes for every item. And you cannot declare an array of pointers as NULL, you muse declare a value for each item. You possibly need to create the tree in reverse, starting with the lowest child elements, and then each successive parent has a single pointer to the chain of children. Alternatively (probably not feasible in your case), make everything dynamic and create it at run time.

Don't know about flash memory or how to initialise it.

Frankie-C · Answer 2 · 2015-05-07T05:59:00

As Richard said it is not possible to make what you want with incomplete types and variable lenght arrays, but ...
If you don't dislike the dark side of the C, there is a workaround:

C++

typedef struct _TreeNode{
    int id;
    char* text;
    struct _TreeNode* children[1]; // List of child nodes
} TreeNode;

static TreeNode tree1 = {1, "child",       {0}};
static TreeNode tree2 = {2, "secondChild", {0}};
static TreeNode tree3 = {3, "thirdChild",  {0}};
static TreeNode tree4 = {4, "fourthchild", {0}};

void *FakeTree[] = {
                     (void *)0,
                     (void *)"hidden",
                     (void *)&tree1,
                     (void *)&tree2,
                     (void *)&tree3,
                     (void *)&tree4
                    };

void DoSth(void)
{
	TreeNode *tree = (TreeNode *)&FakeTree;

	// Code that's actually using the data
	// Please remember that you must access the structure always as a
	// pointer to it. I.e.
	for (int i=0; i<4; i++)
	{
		printf("id=%x, name=\"%s\"\n", pTree->children[i]->id, pTree->children[i]->text);
	}
}

The only limit is that it is mandatory that the integers and the pointers of the machine where you'll use the code have the same size.
Last advice: this could be dangerous for your code, don't make it at home! Jocking, this is how you don't have to make programs, but if it is necessary...
I hope this solves your problem ;)

tree data structure in C

2 solutions

Solution 1

Solution 2

Add your solution here

Preview 0

tree data structure in C

2 solutions

Solution 1

Solution 2

Add your solution here

Preview 0

Existing Members

...or Join us