Building a nary tree in c

Question

I'm trying to create a n-ary tree in C. I'm having issues with populating the tree recursively. I was hoping you could help.

The implementation depends on two functions insert_child and append_child that has been tested and works.

I am trying to build a nary tree recursively. Building it manually works by appending and inserting children to root node created in main. As said, it depends on insert_child() if there is an existing child in the node already and append_child() if there is no existing child in the node.

It currently never stops running and does not output 1 for success.

The entire program:

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

#define MAX_LINE_SIZE 85
#define MAX_NODES 50
#define MAX_CHILDREN 5

// Data
typedef struct {
  int library_choice;
  double probability;
  int child_id; // unique id from 1-n (total)
  int child_index; // index from left in node from 1-n
  int kr; // Antal Kr. Kun available in some cases
  int utility; // Kun available in if Leafnode
} d_child;

typedef struct {
  int node_index; // From 1-n for each level (resets)
  int node_id; // unique id from 1-n (total)
  int n_children; // Number of children in level
  d_child d_child[MAX_CHILDREN];
} d_node;

typedef struct {
  int level_id; // From 1-n
  int player; // From 1-n
  int n_nodes; // From 1-n
  d_node d_node[MAX_NODES];
} d_level;

// Tree
typedef struct s_nary_node {
  d_level data; // nodes data -> comes in index for the level
  int n; // the number of children
  struct s_nary_node **child; // the child list
} nary_node;
typedef nary_node nary_tree;

nary_tree *create_node(int children, d_level *data, int i) {
  // allocate space for new nary_node
  nary_node *node = (nary_node*)calloc(1, sizeof(nary_node));

  // Set the contents of the NODE
  node->data = data[i];
  node->n = children;
  node->child = (nary_node**)calloc(children, sizeof(nary_node*));

  return node;
}

int append_child(nary_node *root, d_level *data, int i) {
  // Increment the degree of the node
  root->n++;

  // Reallocate the child array (n children in the child array)
  root->child = (nary_node **)realloc(root->child,(root->n)*sizeof(nary_node*));

  // Add the newNode into the child array and increment degree
  root->child[root->n - 1] = create_node(0, data, i);

  // Return the index of the child we just inserted
  return root->n - 1;
}

int insert_child(nary_node *root, int idx, d_level *data, int i) {
  int j;

  // First we make space
  root->n++;
  root->child = (nary_node**)realloc(root->child, (root->n)*sizeof(nary_node*));
  for(j=root->n-1; j>idx; --j) 
    root->child[j] = root->child[j-1];
  root->child[j] = create_node(0, data, i);
  return j;
}

int create_tree(nary_node *root, d_level *data, int i) {
  int j = 1;

  if(root->n == 0) return 0; // Terminating condition
  else {
    for(j=1; j<root->n+1; j++) { // For every nodes children
      printf("Hey\n");
      if(root->child[j] == NULL) {
        append_child(root, data, i);
      }
      else { 
        insert_child(root, j, data, i);
      }
      i++; // Count up level for data
      root = root->child[j];
      create_tree(root, data, i);
    }
    return 1;

  } 
}

// Data
int count_levels() {
  int count = 0;
  FILE *input_file; 
  input_file = fopen("data.xml", "r"); 
  if(input_file == NULL) { printf("Could not open file\n"); }
  else {
    char temp[MAX_LINE_SIZE]; 
    char level[] = "<level";
    while(fgets(temp, MAX_LINE_SIZE, input_file)!= NULL) {
      if(strstr(temp, level) != NULL) {
        count++;
      }
    }
  }
  return count;
}

void read_level_data(d_level *d_level){
  char temp[MAX_LINE_SIZE];
  char level[] = "<level";
  int i = 1;

  // Opening file
  FILE *input_file; 
  input_file = fopen("data.xml", "r"); 

  if(input_file == NULL) { printf("Could not open file\n"); }
  else {
    while(fgets(temp, MAX_LINE_SIZE, input_file)!= NULL){
      if(strstr(temp, level)) {
        sscanf(temp, "<level id=\"%d\" player=\"%d\"  nNodes=\"%d\">", &d_level[i].level_id, &d_level[i].player, &d_level[i].n_nodes);
        i++;
      }
    }
  }
}

void read_node_data(d_level *d_level){
  char temp[MAX_LINE_SIZE];
  char node[] = "<node";
  char end_node[] = "</node";
  char end_level[] = "</level>";

  int i = 1;
  int j = 1;
  // Opening file
  FILE *input_file; 
  input_file = fopen("data.xml", "r"); 

  if(input_file == NULL) { printf("Could not open file\n"); }
  else {
    while(fgets(temp, MAX_LINE_SIZE, input_file)!= NULL){
      if(strstr(temp, node)) {
        sscanf(temp, " <node idx=\"%d\" id=\"%d\" nChildren=\"%d\">", &d_level[i].d_node[j].node_index, &d_level[i].d_node[j].node_id, &d_level[i].d_node[j].n_children);
      } 
      else if(strstr(temp, end_node)) {
        j++;
      }
      else if(strstr(temp, end_level)) {
        i++;
        j = 1; // reset nodecount for each iteration
      }
    }
  }
}

void read_child_data(d_level *d_level){
  char temp[MAX_LINE_SIZE];
  char child[] = "<child";
  char library_choice[] ="<libraryChoice";
  char probability[] = "<probability";
  char utility[] = "<probability";
  char kr[] = "<kr";
  char end_child[] = "</child";
  char end_node[] = "</node";
  char end_level[] = "</level";

  int i = 1;
  int j = 1;
  int k = 1;

  // Opening file
  FILE *input_file; 
  input_file = fopen("data.xml", "r"); 

  if(input_file == NULL) { printf("Could not open file\n"); }
  else {
    while(fgets(temp, MAX_LINE_SIZE, input_file)!= NULL){
      if(strstr(temp, child)) {
        sscanf(temp, " <child idx=\"%d\" id=\"%d\">", &d_level[i].d_node[j].d_child[k].child_index, &d_level[i].d_node[j].d_child[k].child_id);
      } 
      else if(strstr(temp,library_choice)) {
        sscanf(temp, " <libraryChoice>%d</libraryChoice>", &d_level[i].d_node[j].d_child[k].library_choice);
      } 
      else if(strstr(temp,probability)) {
        sscanf(temp, " <probability>%lf</probability>", &d_level[i].d_node[j].d_child[k].probability);
      } 
      else if(strstr(temp,utility)) {
        sscanf(temp, " <utility>%d</utility>", &d_level[i].d_node[j].d_child[k].utility);
      } 
      else if(strstr(temp,kr)) {
        sscanf(temp, " <kr>%d</kr>", &d_level[i].d_node[j].d_child[k].kr);
      }
      else if(strstr(temp, end_child)) { // </child
        k++;
      }
      else if(strstr(temp, end_node)) { // </node
        j++;
        k = 1;
      } 
      else if(strstr(temp, end_level)) { // </level
        i++;
        j = 1;
      }
    }
  }
}

int main(void) {
  // Data
  d_level *d_level =  calloc(count_levels(), sizeof(1, d_level));

  // Read level data
  read_level_data(d_level);

  // Read node data
  read_node_data(d_level);

  // Read children data
  read_child_data(d_level);

  int i = 1; 
  nary_tree* root = (nary_node*)calloc(count_levels(),sizeof(nary_node));
  root = create_node(2, d_level, i);
  nary_tree* temp = (nary_node*)calloc(count_levels(),sizeof(nary_node));
  temp = root;
  int success = create_tree(temp, d_level, i);
  printf("Return value: %d\n", success);
}

The XML input i am parsing:

<level id="1" player="1" nNodes="1">
  <node idx="1" id="1" nChildren="2">
    <child idx="1" id="1">
      <libraryChoice>1</libraryChoice>
      <kr>1000</kr>
    </child>
    <child idx="2" id="2">
      <libraryChoice>2</libraryChoice>
      <kr>2000</kr>
    </child>
  </node>
</level>

<level id="2" player="2" nNodes="2">
<node idx="1" id="2" nChildren="2">
<child idx="1" id="3">
  <libraryChoice>1</libraryChoice>
  <probability>50.0</probability>
</child>
<child idx="2" id="4">
  <libraryChoice>2</libraryChoice>
  <probability>50.0</probability>
</child>
</node>
<node idx="2" id="3" nChildren="2">
<child idx="1" id="5">
  <libraryChoice>3</libraryChoice>
  <probability>50.0</probability>
  <utility>-100</utility>
  <kr>3000</kr>
</child>
<child idx="2" id="6">
  <libraryChoice>4</libraryChoice>
  <probability>50.0</probability>
  <utility>100</utility>
  <kr>4000</kr>
</child>
</node>
</level>

<level id="3" player="1" nNodes="2">
<node idx="1" id="4" nChildren="0">
</node>
<node idx="2" id="5" nChildren="0">
</node>
<node idx="3" id="6" nChildren="0">
</node>
<node idx="4" id="7" nChildren="0">
</node>
</level>

Answer 1

In main():

d_level *d_level =  calloc(count_levels(), sizeof(1, d_level));

The argument to sizeof is wrong here. Lets ignore the "1," first, it doesn't do anything. With sizeof(d_level), you probably meant to get the size of the struct d_level. However, you have already redeclared it to be a variable of type d_level *. So sizeof(d_level) here will return the size of a pointer, not of a struct. It's better to do:

d_level *d_level = calloc(count_levels(), sizeof *d_level);

Next problem is in read_level_data():

int i = 1;
...
while(fgets(temp, MAX_LINE_SIZE, input_file)!= NULL){
  if(strstr(temp, level)) {
    printf("%i\n", i);
    sscanf(temp, "<level id=\"%d\" player=\"%d\" nNodes=\"%d\">", &d_level[i].level_id, &d_level[i].player, &d_level[i].n_nodes);
    i++;
  }
}

You are starting your index i at 1. However, in C, arrays start counting at 0. Use int i = 0 instead. You make the same mistake in the other functions as well.

Then there is create_tree(). It recursively calls itself. However, in these two lines:

  root = root->child[j];
  create_tree(root, data, i);

It can happen that root->child[j] is NULL, which means you call create_tree() with a NULL pointer, causing a segmentation fault. Also, you are modifying the variable root, which is maybe not what you want. It's better to do:

  if(root->child[j])
    create_tree(root->child[j], data, i);

There are even more problems after this.

Compile your code with warnings enabled, and fix any warnings you find first. Then, use a debugger to analyze segmentation faults, or use tools like valgrind to catch memory access problems. And being more careful when you are coding should prevent bugs like this in the first place.