c++ - 当我尝试构建八叉树结构时堆栈溢出

Question

我想构建一棵 n 维树。我使用 vector 来存储每个节点的子节点。我写的代码给出了“stack overflow error”，我不知道为什么，我确实使用了new。如果有人能告诉我哪里出错了，我将不胜感激。

class Node
{
public:
  int q_number;
  int layer;
  int value;
  vector<Node*> n_list;

  Node(int n):q_number(n),n_list(n) //initialize node vector
  {
  }
};

Node* buildtree(int n,int depth)
{
  Node * node = new Node(depth);

  if(n==depth-1)
  {
    for(int i = 0; i<depth;i++)
    {
      node->n_list[i] = NULL;
      node->n_list[i]->value = i;
      node->n_list[i]->layer = depth-1;
    }
  }
  else
  { 
    for (int i =0;i<depth;i++)
    {               
      node->n_list[i] = buildtree(n++,depth);// span the tree recursively           
      node->n_list[i]->value = i;
      node->n_list[i]->layer = n;   // the layer value
    }
  }

  return node;
}
int main()
{
  Node * tree = buildtree(0,8); // build an octree
}

Answer 1

作为Dolda2000注意到，您后递增n 调用 buildtree 时递归地。因此，n 在其旧值(未更改)传递给函数后递增。因此，您有无限堆 buildtree(0,8);调用，这自然会导致堆栈溢出。

前递增 — buildtree(++n,depth); — 会解决堆栈溢出问题，但在这种情况下不是您想要的，因为您使用了 n在递归调用之后。据我了解您的意图，您不期望 n 的值(value)在递归调用后更改。

您的情况的解决方案是:

buildtree(n+1,depth);

---

您的代码中还有另一个问题:

    node->n_list[i] = NULL; // ok, the pointer is NULL now
    node->n_list[i]->value = i; // trying to dereference a NULL pointer => error
    node->n_list[i]->layer = depth-1;

您需要一个 new Node(...)在这里，或从 Node* 更改 vector 的值类型至 Node , ... 或确保指针在取消引用之前已正确设置。

附言并确保 n <= depth-1 — 通过断言，或至少在代码中包含注释以避免以后进行大量调试。