在C++中遍歷一棵普通的樹

我試圖遍歷一棵普通的樹。爲了這個例子的目的，我有這個結構來保存我的孩子和父母關係。在C++中遍歷一棵普通的樹

struct DataItem { 
    int id; 
    DataItem* root; 
    vector<DataItem*> children; 
};

與二叉樹遍歷相比，我沒有使用* left和* right，因爲可能有多個節點。爲了遍歷代碼，我使用了這兩個方法，分別叫做constructMap和traverseTree。

void traverseTree(std::vector<int>::iterator current, std::vector<int>::iterator end, 
    std::vector<int>::iterator next, DataItem *root) { 
    while (current != end) { 
     DataItem *childNode; 
     childNode->id = *current; 
     childNode->root = root; 
     if (*current + 1 == *next) { 
      root->children.push_back(childNode); 
     } else { 
      // traverse the next tree 
      traverseTree(++current, end, ++next, childNode); 
     } 
     ++next; 
     ++current; 
    } 
} 


void constructMap(std::vector<int>::iterator start, std::vector<int>::iterator end) { 
    auto next = std::next(start, 1); 
    DataItem *parentNode; 
    parentNode->id = *start; 
    parentNode->root = NULL; 
    traverseTree(++start, end, ++next, parentNode); 
    cout << " at the end " << endl; 
}

我還沒有測試邏輯看穿越其實是功能性的，但我相信它不是，但我不斷收到以下錯誤：

Segmentation fault (core dumped)

經過一番註釋掉，事實證明這發生在constructMap，當調用此調用：

parentNode->id = *start;

如果我做這樣的事情，而不是：

int val = *start; 
parentNode->id = val;

我能夠通過此分段故障並繼續前進。

我傳遞一個向量的迭代器我的地圖過程中，含有這樣的事情：1,3,4,5,7,8,10

constructMap(allNumbers.begin(), allNumbers.end());

來源

2016-07-07 angryip

*經過一番評論，* - 所以你沒有使用調試器？ – PaulMcKenzie

的問題是，你試圖訪問未初始化的指針parentNode。也許這是一個簡單的對象：

DataItem parentNode; 
parentNode.id = *start; 
parentNode.root = NULL; 
traverseTree(++start, end, ++next, &parentNode);

來源

2016-07-07 18:30:22 tsandy

tsandy是正確的，我想。我有點擔心看到std :: next使用了start，並且在事實之後直接從它獲得值。問題是，如果std :: next advance開始或者沒有開始，我不記得。 – Andrew

@Andrew當我查看std :: next的文檔時，所有提到的內容都是指向迭代器的原始指針被複制並遞增，而不是訪問並增加 – angryip

@Andrew如果它會提高指針，它會等同於運算符++（），因此是多餘的。事實上，我不知道任何標準庫函數通過非const引用接受迭代器參數並對其進行變異。 –

在C++中遍歷一棵普通的樹

回答

相關問題