Implement N-ary Tree in c

Question

I'm trying to implement a N-ary tree in C. I know how to implement if I decide how many childs would have earlier. But my problem is, i want to make it dynamic (i want to resize the children and child size)

struct node    
{
    char * type;
    struct node **child;
    int children;
    int id;    
};

this is my struct and i want to do that with a pointer of pointer. How can i implement the insertion function?

        struct node **toKeep = (*root)->child;
        (*root)->children+=1;
        (*root)->child =malloc(sizeof(struct node*)*
        (*root)->child = toKeep;
        size_t i; 
        for (i= 0; i < (*root)->children; i++)
        {
            if ((*root)->child[i] == NULL)
            {
                (*root)->child[i] = newNode(type, id);
                printf("%d \n", (*root)->child[i]->id);
                break;
            }
        }

i tried this to keep existing nodes but im unable to add more than 2 nodes ? What can cause the problem or is there a better way to write it?

Does this answer your question? [N-ary trees in C](https://stackoverflow.com/questions/189855/n-ary-trees-in-c) — bvpb, Jun 01 '20 at 00:47
Your `struct` is correct for a dynamic array based implementation. But `(*root)->anything` is suspicious. Instead of `malloc`, you want `realloc` (e.g.) `curnode->children += 1; curnode->child = realloc(curnode->child,sizeof(struct node *) * curnode->children); curnode->child[curnode->children - 1] = NULL;` — Craig Estey, Jun 01 '20 at 00:55
But, now that I think of it, shouldn't your `struct node` have a pointer to its _parent_ node (e.g. `struct node *parent;`)? — Craig Estey, Jun 01 '20 at 01:00
I look that link answer but i wanna use only **child, Because it costs less space in RAM. I tried something but still it has some bug. — Burak kaya, Jun 02 '20 at 15:05

Craig Estey · Answer 1 · 2020-06-02T19:19:01.147

This is prefaced by my top comments.

Since I couldn't understand the intent of your code fragment, I refactored the code based on a trie example I've done before. It may or may not be what you're looking for, but, at least, the dynamic child list code should give you an idea:

#include <stdlib.h>

typedef struct node node_t;
struct node {
    char *type;

    node_t *parent;
    node_t **child;
    int children;

    int id;
};

// naryfind -- find matching child node based on id
node_t *
naryfind(node_t *par,int id)
{
    size_t cldidx;
    node_t *cld;
    node_t *match;

    match = NULL;

    for (cldidx = 0;  cldidx < par->children;  ++cldidx) {
        cld = par->child[cldidx];

        // skip empty slot
        // NOTE: this will probably never happen based on naryattach
        if (cld == NULL)
            continue;

        if (cld->id == id) {
            match = cld;
            break;
        }
    }

    return match;
}

// narynew -- get new node
node_t *
narynew(int id)
{
    node_t *node;

    node = calloc(1,sizeof(node_t));
    node->id = id;

    return node;
}

// naryattach -- attach new child node
node_t *
naryattach(node_t *par,int id)
{
    size_t cldidx;
    node_t *cld;

    // increase size of array
    cldidx = par->children++;
    par->child = realloc(par->child,sizeof(node_t *) * par->children);

    // allocate new node
    cld = narynew(id);

    // cross-link parent and child
    cld->parent = par;
    par->child[cldidx] = cld;

    return cld;
}

// naryfindx -- find matching child node (create new node if none found)
node_t *
naryfindx(node_t *par,int id)
{
    node_t *cld;

    // find existing node
    cld = naryfind(par,id);

    // create new node if it doesn't already exist
    if (cld == NULL)
        cld = naryattach(par,id);

    return cld;
}

Implement N-ary Tree in c

1 Answers1

Linked