0

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;
}
20
  • Please provide a minimal reproducible example. In particular, the main that initialises root and calls create_tree. Commented Dec 17, 2016 at 22:11
  • root->data.n is not assigned in posted code, yet used in for(i=0; i<root->data.n; i++) Commented Dec 17, 2016 at 22:13
  • Im sorry for the late edit. Just added the main() and create_node() function that main depends on to create the root node. It should compile exacly as on my machine if you copy the code now. @kaylum Commented Dec 17, 2016 at 22:16
  • @chux Im sorry. Have added context so you can see the assignment. It is in create_node() that is called in main and indirectly in append_children() because it calls create_node(). Commented Dec 17, 2016 at 22:17
  • What does your data contain? It is not initialised in the posted code. Commented Dec 17, 2016 at 22:17

1 Answer 1

1

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'.

Sign up to request clarification or add additional context in comments.

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.