how to create a n-ary tree in c

Question

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


struct node{
  char *word;
  int depth, children;
  struct node  **child;
};

typedef struct node node;


node *createTree();
node *createNode(char *word,int depth);

int main(int argv,char *argc[]){
   node *root,*current_node;
   root=createNode("root",0);
   char *array[]={"string1","string2","string3"};
   current_node=root;
   printf("root has been created with word: %s \n",current_node->word);
   int i;
   for (i=0; i<3; i++){
      current_node->child[i]=createNode(array[i],(current_node->depth)+1);
      current_node->children++;
      printf("%s  has been inserted to the tree\n",current_node->word);
   }

}



node *createTree(){
   printf("root has been created\n");
   return createNode("",0);    /*creates the first node*/
}

node *createNode(char *word,int depth){
   node *new_node;
   new_node=malloc(sizeof(node));
   new_node->word=word;
   new_node->depth=depth;
   new_node->children=0;
   new_node->child=NULL;
}

So what i am trying to do here is build a n-ary tree. I use createNode function to create the children of the root but as soon as i am trying to link an adress of a new node to a child, the program crashes with segmentation fault. I know my mistake probably is,the way i try to create the children but i cant find. Help anyone?

Solution

Just allocate memory for the child struct member before using it:

current_node->child = malloc(3 * sizeof(node *));

for (i=0; i<3; i++) {
    current_node->child[i] = createNode(array[i],(current_node->depth)+1);
    current_node->children++;
    printf("%s  has been inserted to the tree\n",current_node->word);
}

The structure you've defined means you have to manage each level as an array of nodes with a potentially dynamic number of elements. A more common structure used for n-ary tree representation in C would be:

struct node {
    char *word;
    int depth, children;  // Reconsider if you need these
                          //   for maintenance effort versus benefit
    struct node *child;   // point to children of this node
    struct node *next;    // point to next node at same level
};

So the structure looks like this:

Root -> NULL
 |
 V
Child-1.1 -> Child-1.2 -> ... -> Child-1.n -> NULL
 |              |                   |            
 |              V                   V
 |              ...              Child-1.n.1 -> ... -> NULL
 V
Child-1.1.1 -> Child-1.1.2 -> ... -> NULL
 |
 ... etc

You'd then need to modify your createNode and write your other tree management routines accordingly. A partial and very terse sample of how they might look would be (not necessarily containing all the right validity checks or node removal/deallocations):

struct node {
    int data;
    struct node *next;
    struct node *child;
};

typedef struct node node;

node * new_node(int);
node * add_sibling(node *, int);
node * add_child(node *, int);

int main(int argc, char *argv[])
{
    int i;
    node *root = new_node(0);

    for ( i = 1; i <= 3; i++ )
        add_child(root, i);
}

node * new_node(int data)
{
    node *new_node = malloc(sizeof(node));

    if ( new_node ) {
        new_node->next = NULL;
        new_node->child = NULL;
        new_node->data = data;
    }

    return new_node;
}

node * add_sibling(node * n, int data)
{
    if ( n == NULL )
        return NULL;

    while (n->next)
        n = n->next;

    return (n->next = new_node(data));
}

node * add_child(node * n, int data)
{
    if ( n == NULL )
        return NULL;

    if ( n->child )
        return add_sibling(n->child, data);
    else
        return (n->child = new_node(data));
}

Comments

[Hlias A.]

Thank you very much. I used the structure you pointed out. That was really helpful. Could please also tell me a way to print or search for a node in this data structure? I am fairly new to C and particularly data structures and i am having a hard time.

[lurker]

@HliasA. I think if you study this structure a little, you can figure this out. It's just based upon simple linked lists where you can follow the links until you see NULL (the add_sibling function is an example of that). To print the whole structure, you'd need to decide if you are doing breadth-first or depth-first traversal. But it's the same idea: just follow the links and print at each step of the way. I'll leave that part as an exercise. Keep trying a bit and if you have a specific implementation and are stuck, you can post another question about it.

[user405369]

Thank you very much for showing the right data structure to use..