我的DFS樹意外的結果（C++）

我已經解決了這個問題！我發現如果我必須使用vector<Node*> children;。但是我不太確定原因，有人能告訴我爲什麼嗎？謝謝:)我的DFS樹意外的結果（C++）

問：

我用test.cpp產生相似的樹型結構：

enter image description here

的(ROOT->children).size()結果是2，因爲root有兩個孩子。

((ROOT->children)[0].children).size()的結果應該是2，因爲root的第一個孩子有兩個孩子。但答案是0，爲什麼？它真的讓我困惑。

TEST.CPP（此代碼是可以運行在Visual Studio 2010）

#include <iostream> 
#include <vector> 
using namespace std; 

struct Node { 
    int len; 
    vector<Node> children; 
    Node *prev; 
    Node(): len(0), children(0), prev(0) {}; 
}; 

class gSpan { 
public: 
    Node *ROOT; 
    Node *PREV; 
    void read(); 
    void insert(int); 
}; 

int main() { 
    gSpan g; 
    g.read(); 
    system("pause"); 
} 

void gSpan::read() { 
    int value[4] = {1, 2, 2, 1}; 
    ROOT = new Node(); 
    PREV = ROOT; 
    for(int i=0; i<4; i++) { 
     insert(value[i]); 
    } 
    cout << "size1: " << (ROOT->children).size() << endl; // it should output 2 
    cout << "size2: " << ((ROOT->children)[0].children).size() << endl; // it should output 2 
    system("pause"); 
} 

void gSpan::insert(int v) { 

    while(v <= PREV->len) 
     PREV = PREV->prev; 
    Node *cur = new Node(); 
    cur->len = v; 
    cur->prev = PREV; 
    PREV->children.push_back(*cur); 
    PREV = cur; 

}

來源

2012-03-20 LoveTW

的問題是，你children載體包含Node值，而不是Node*指針。雖然您的訪問權限正確地使用了根，但它只能找到您嘗試維護的子項的副本。你所有的節點也被泄露。

您可能希望爲子女使用std::vector<Node*>，並在某些時候使用delete。最簡單的方法可能是使用一個智能指針向量，例如一個計數指針的計數，並有智能指針照顧釋放。

來源

2012-03-20 07:11:23

我不明白這句話的意思：「它只能找到你想要維護的孩子的副本。你所有的節點也被泄漏。如果我使用'vector children'，那麼'Node'對象應該在兒童中，如果我push_back它。但爲什麼它消失了？感謝您的回覆。 – LoveTW 2012-03-20 07:28:33

你不會把'Node'放在那裏，而是指向它的副本。在C++中，對象是values，而不是指針。如果你爲每個節點對象繪製一個矩形，並且爲每個節點繪製一個箭頭到對應的節點，你可能會看到問題：當你push_back（）你的'* cur'時，你把一個新的'Node '（即一個矩形）插入到「子女」矢量中，但你有莫箭頭。稍後添加小孩時，您可以通過箭頭進行更改，但是當您嘗試查看通過陣列查看的大小時。 – 2012-03-20 07:37:26

感謝您的回覆！最好的祝願：） – LoveTW 2012-03-20 07:46:16

我的DFS樹意外的結果（C++）

回答

相關問題