CODEWITHSUNDEEP
crecursion
John Lag
John Lag

Reputation: 51

Recursive function to create tree

I am trying to create a function that creates a tree with recursion but I keep getting a segmentation fault each time I try. I have created the following function. Can you help me understand what is going wrong and how I can fix it? The data is stored from 1 and up in a data[i] array.

void create_tree(nary_node* root, data *data)
{
  if(root == NULL) return;

  int i;
  static int datacount; 

  for(i=0; i<root->data.n; i++) { // For each child in the root
    append_child(root, data[datacount]);
    create_tree(root->child[i], data);
  }
}

It depends on a helper function append_child():

void append_child(nary_node *root, data data)
{
  int i = 0;
  while (root->child[i] != NULL) i++;

  root->child[i] = create_node(data.n, data);
}

The manual tree construction would be as follows: 

append_child(root, data[1]);
append_child(root, data[2]);
append_child(root->child[0], data[3]);
append_child(root->child[0], data[4]);
append_child(root->child[1], data[5]);
append_child(root->child[1], data[6]);

This would create a tree with two nodes from root with two children each. It works fine manually, but I am having trouble with the recursive part.

Just added structs for and explainations for context if needed:

/*
  Data contains all possible data for each node 
*/
typedef struct 
{
  int n;  // Number of children
} data;

/* 
  nary_node contains each nodes data and an array of pointers
  to it's children. An arbitrary max-value was set to 10-children.
*/
typedef struct s_nary_node 
{
  data data;
  struct s_nary_node* child[10];
} nary_node;

in main():

int main(void) {
   data data[99];
   nary_node *root = create_node(data[0].n, data[0]);
   create_tree(root, data);
}

in create_node():

nary_node *create_node(int children, data data)
{
  int i = 0;
  nary_node *node = (nary_node*)malloc(sizeof(nary_node));

  for (i = 0; i < 10; i++)
    node->child[i] = NULL;

  node->data = data;
  node->data.n = children;
  return node;
}

Upvotes: 0

Views: 1457

Answers (1)

Krzak
Krzak

Reputation: 1461

If you follow the recursion calls you will notice that it expands as follows:

append_child(root, data[0]);
append_child(root->child[0], data[0]);
append_child(root->child[0]->child[0], data[0]);
append_child(root->child[0]->child[0]->child[0], data[0]);
[...]
append_child(root->child[0]->[...]->child[0]->child[0], data[0]);

As you never increase the datacount and apparently in your example data[0].n == 2 Although a simple postincrementation won't give you the expected result, because it will expand instead into:

append_child(root, data[1]);
append_child(root->child[0], data[2]);
append_child(root->child[0]->child[0], data[3]);
append_child(root->child[0]->child[0]->child[0], data[4]);
[...]
append_child(root->child[0]->[...]->child[0]->child[0], data[?]);

Instead try this:

void create_tree(nary_node* root, data *data)
{
    if(root == NULL) return;

    int i;
    static int datacount = 1; 

    for(i=0; i<root->data.n; i++) { // For each child in the root
        append_child(root, data[datacount++]);
    }
    for(i=0; i<root->data.n; i++) {
        create_tree(root->child[i], data);
    }
}

Not as elegant, but should provide you with the same result as your expected manual 'creation'.

Upvotes: 1

Related Questions