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

问题描述

我已经解决了这个问题！！！我发现如果我必须使用 vector儿童；.但我不是很确定原因，有人能告诉我为什么吗?谢谢:)

I have solved this problem!!! I found that if i have to use vector<Node*> children;. But I am not very sure the reason, can someone tell me why? Thanks:)

问题:

我使用 test.cpp 生成一个树结构，如:

I use test.cpp to generate a tree structure like:

(ROOT->children).size() 的结果是 2，因为 root 有两个孩子.

The result of (ROOT->children).size() is 2, since root has two children.

((ROOT->children)[0].children).size() 的结果应该是 2，因为 的第一个孩子root 有两个孩子.但答案是0，为什么呢?这让我很困惑.

The result of ((ROOT->children)[0].children).size() should be 2, since the first child of root has two children. But the answer is 0, why? It really confuse for me.

test.cpp(此代码可在 Visual Studio 2010 中运行)

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;

}

推荐答案

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