c - 递归函数创建树

Question

我正在尝试创建一个函数来创建具有递归的树，但每次尝试时我都会遇到段错误。我创建了以下函数。您能帮助我了解出了什么问题以及如何解决它吗？数据从 1 开始存储在 data[i] 数组中。

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);
  }
}

这取决于辅助函数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);
}

手动树构建如下:

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]);

这将创建一棵树，其中从根开始有两个节点，每个节点有两个子节点。它手动工作正常，但我在递归部分遇到问题。

如果需要，只需添加上下文的结构和解释:

/*
  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;

在 main() 中:

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

在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;
}

Answer 1

如果您遵循递归调用，您会发现它扩展如下:

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]);

因为您从未增加datacount，并且显然在您的示例中data[0].n == 2尽管简单的后增量不会给您预期的结果，因为它会扩展为:

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[?]);

试试这个:

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);
    }
}

不太优雅，但应该为您提供与预期的手动“创建”相同的结果。