從指令缺席兒童的預訂遍歷的二叉樹

我有一個預先遍歷的二叉樹，它看起來像這樣：{1 4 6 10 0 0 0 7 0 8 0 0 2 5 0 0 3 9 0 0 0 }，其中一個0表示沒有子元素。從指令缺席兒童的預訂遍歷的二叉樹

如何從這些數據構建原始二叉樹？我試圖解決遞歸問題，但我還沒有意識到如何處理節點的正確子節點，因爲我不能計算它們在數組中的位置，除非它們有一個葉子作爲父節點（葉子有之後有兩個零，這表明它沒有孩子）。

我覺得這個解決方案非常簡單，但仍然沒有看到它。

來源

2016-01-29 AWhite

*除非他們有葉子作爲父母*。葉子如何能成爲父母？你不覺得這與葉子是矛盾的嗎？ – Atri

它不可能，但我的意思是葉子在它後面有兩個零的情況，這表明它沒有孩子。 – AWhite

葉子在它後面有2個零時，如果當前元素本身不是正確的元素並且繼續以遞歸方式檢查，那麼下一個元素將是其父元素的右元素。明白了我的觀點？ – Atri

像這樣簡單的東西可能適合你。您只需要按照輸入序列的預先解釋重新構建樹。以下代碼不會驗證輸入序列以檢查它是否是有效的樹形表示。

struct BTNode { 
    int data; 
    BTNode* left; 
    BTNode* right; 
} 

BTNode* BuildTree(int* sequence, int& pos) { 
    int value = sequence[pos++]; 
    if (value == 0) 
     return nullptr; 
    BTNode* node = new BTNode; 
    node->data = value; 
    node->left = BuildTree(sequence, pos); 
    node->right = BuildTree(sequence, pos); 
    return node; 
}

來源

2016-01-29 20:32:01 Fede

這是soooooo明顯，不知道我怎麼沒有想出它:(非常感謝你。 – AWhite

從指令缺席兒童的預訂遍歷的二叉樹

回答

相關問題