當我嘗試構建八叉樹結構時堆棧溢出

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 - 通過斷言，或者在代碼中包含註釋，至少可以避免以後進行大量調試。