c - 递归构建n叉树时如何确保数据索引正确

Question

鉴于:我有一个连续存储的数据数组，其中包含每个节点的数据。所需的树结构如下图所示，其中所有数字都是节点 ID。

如何递归构造n叉树？

         0
    ------------
    1          2
  / | \      / | \
 3  4  5    6  7  8
/ \
9  10 ....... And so on

这是我尝试制作的函数实现:

void tree_constructor(nary_node* root, data *data)
{
  int i = 0;
  static int datacount = 1;

  if(root == NULL) return;

  if(root->data.children) {
    for(i=0; i<root->data.children; i++)
      append_child(root, data[datacount++]);

    for(i=0; i<root->data.children; i++)
      tree_constructor(root->child[i], data);
  }
}

我认为可以通过实现一个队列来解决这个问题，在队列中以某种方式存储函数调用，并且仅在第一个函数完成后才执行其他子递归函数调用。但实现起来仍然遇到困难。我仍然不确定这是否是最好的解决方案。

仅打印我的左子树的结果:0 1 3 4 5 6 7 8 13 14 15 16 17 18

预计:0 1 3 4 5 6 11 12 13 14 15 16 17 18

最小示例测试:(准备编译)

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

#define MAX_CHILDREN 10
#define MAX_DATA 100

typedef struct data {
  int children;
  int id;
} data;

typedef struct nary_node {
  // Data element to hold data.
  data data;
  // Array of pointers to the children.
  struct nary_node* child[MAX_CHILDREN];
} nary_node;

void tree_constructor(nary_node* root, data *data);
nary_node *create_node(int children, data data);
void append_child(nary_node *root, data data);
void manual_print(nary_node *root);

int main() 
{
  int i;

  nary_node *root;

  data data[MAX_DATA];

  // The test-case data
  // Id's
  for(i=0; i<MAX_DATA; i++) data[i].id = i;

  // Children
  data[0].children = 2;
  data[1].children = 4;
  data[2].children = 4;
  for(i=3; i<=8; i++) data[i].children = 2;

  root = create_node(data[0].children, data[0]);

  tree_constructor(root, data);

  manual_print(root);

}

void tree_constructor(nary_node* root, data *data)
{
  int i = 0;
  static int datacount = 1;

  if(root == NULL) return;

  if(root->data.children) {
    for(i=0; i<root->data.children; i++)
      append_child(root, data[datacount++]);

    for(i=0; i<root->data.children; i++)
      tree_constructor(root->child[i], data);
  }
}

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

  //Memory for a new node is allocated.
  nary_node *node = (nary_node*)malloc(sizeof(nary_node));

  //All children is set to NULL.
  for (i = 0; i < MAX_CHILDREN; i++)
    node->child[i] = NULL;

  //The nodes data element is assigned to the input data element.
  node->data = data;

  //The n variable in data is assigned to the number of children.
  node->data.children = children;

  //The node is returned.
  return node;
}

void append_child(nary_node *root, data data)
{
  int i = 0;

  // A while loop to find the right index to append a child.
  while (root->child[i] != NULL) i++;

  // A new node is created at the last index.
  root->child[i] = create_node(data.children, data);
}

void manual_print(nary_node *root) 
{
  printf("%d\n", root->child[0]->data.id);
  printf("%d\n", root->child[1]->data.id);

  // Print left subtree for test
  printf("%d\n", root->child[0]->child[0]->data.id);
  printf("%d\n", root->child[0]->child[1]->data.id);
  printf("%d\n", root->child[0]->child[2]->data.id);
  printf("%d\n", root->child[0]->child[3]->data.id);

  printf("%d\n", root->child[0]->child[0]->child[0]->data.id);
  printf("%d\n", root->child[0]->child[0]->child[1]->data.id);
  printf("%d\n", root->child[0]->child[1]->child[0]->data.id);
  printf("%d\n", root->child[0]->child[1]->child[1]->data.id);
  printf("%d\n", root->child[0]->child[2]->child[0]->data.id);
  printf("%d\n", root->child[0]->child[2]->child[1]->data.id);
  printf("%d\n", root->child[0]->child[3]->child[0]->data.id);
  printf("%d\n", root->child[0]->child[3]->child[1]->data.id);
}

Answer 1

队列的想法是正确的。只是不要递归。

创建nary_node *队列。通过创建根并将指针插入队列来启动该进程。然后重复从节点中拉出指针，并创建其子节点，同时推送它们的指针:

    while (!empty(queue)) {
        nary_node * node = pull_node(queue);
        for (i = 0; i < node->data.children; i++) {
            node->child[i] = create_node(data++);
            push_node(queue, node->child[i]);
        }
    }