How to deal with Tree with several branchs?

[Davy]

My program deal with a several level tree with several branchs. The
amount of branchs from father node is not known. So I want to creat a
tree with dynamic branchs.

Now I use the structure:
typedef struct gnodes
{
int level; //tree level
struct gnodes* pfather;
struct gnodes* pbrother;
struct gnodes* pchild;
struct gnodes* puncle;
} gnode;

The child pointer link one by one form a chain, something like:
Father(i)->Child(1)->Child(2)->...->Child(n-1)->Child(n).
But I can not search child randomly.

How to design a better structure?
Any suggestions will be appreciated!

Best regards,
Davy

 

[Malcolm]

My program deal with a several level tree with several branchs. The
amount of branchs from father node is not known. So I want to creat a
tree with dynamic branchs.

Now I use the structure:
typedef struct gnodes
{
int level; //tree level
struct gnodes* pfather;
struct gnodes* pbrother;
struct gnodes* pchild;
struct gnodes* puncle;
} gnode;

The child pointer link one by one form a chain, something like:
Father(i)->Child(1)->Child(2)->...->Child(n-1)->Child(n).
But I can not search child randomly.

How to design a better structure?
Any suggestions will be appreciated!

You need an arbitrary number of children. You choice is to use a list of
pointers allocated with malloc(), or to use a linked list.

For the former, have a member

struct gnodes **children;
int Nchildren;


For the latter

struct gnodes *child1;
struct gnodes *sibling;

The last child in the chain has a NULL sibling.

Neither structure is ideal. The first will consume time for allocations, and
you will also have annoying nuisance code to deal with memory running out.
The second cannot be searched quickly.

If the number of children is very large, you could try something more
elaborate, like a balanced binary search tree, to hold the children. However
it does have to be very large to justify this.