c++ - 我的 DFS 树 (C++) 的意外结果

Question

我已经解决了这个问题!!!我发现如果我必须使用 vector<Node*> children; .但是我不太确定原因，有人可以告诉我为什么吗？谢谢:)

问题:

我使用 test.cpp生成如下树结构:

(ROOT->children).size() 的结果是2 , 自 root有两个 child 。

((ROOT->children)[0].children).size() 的结果应该是 2 , 自 root 的第一个 child 有两个 child 。但答案是0 ， 为什么？这让我很困惑。

test.cpp (This code is runnable in 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;

}

Answer 1

问题是你children vector 包含Node值而不是 Node*指针。虽然您的访问正确使用了根，但它只会找到您尝试维护的子项的拷贝。您的所有节点也都已泄露。

您可能想使用 std::vector<Node*>为了您的 child 和delete他们在某个时候。最简单的方法可能是使用智能指针 vector ，例如一个引用计数指针，并让智能指针负责释放。