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

Question

我想构建一个n维树。我使用vector来存储每个节点的子节点。我写的代码给出了“堆栈溢出错误”，我不知道为什么，我使用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注意到，你是后递增调用buildtree当递归n。因此，在之后n递增其旧值（不变）已被传递给函数。因此，你有一堆无限的buildtree(0,8);调用，这自然会导致堆栈溢出。

预 -incrementing - buildtree(++n,depth); - 将解决堆栈溢出问题，但是这并不你在这种情况下想要的东西，因为你做的递归调用使用后的n。根据我的理解你的意图，你不希望递归调用后n的值改变。

你的情况的解决方案就是：

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*改变向量的值类型到Node，...或确保指针在解除引用前正确设置。

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