構造給定的二叉樹Post order

如果只有給出的信息是後序遍歷，如何構造二叉樹。通過搜索主題，我明白在這種情況下，不可能有獨特的構造二叉樹。但是，如果給定整數，則基於更少或更大的屬性來創建BT變得容易。但是，如果我們有字母表，那麼我無法弄清楚我們是以什麼爲基礎製作父節點的左節點或右節點。這是我試圖解決的問題。構造給定的二叉樹Post order

Q）二叉樹的後序遍歷是DEBFCA。找出預序遍歷嗎？

選項：
（A）ABFCDE
（B）ADBFEC
（C）ABDECF
（0）ABDCEF

正確答案是：C

有人能解釋我們如何到達回答。

我發現這個答案https://www.quora.com/If-the-post-order-traversal-of-a-binary-tree-is-DEBFCA-how-can-I-find-out-the-pre-order-traversal/answer/Eugene-Yarovoi?srid=zy7j非常有幫助，但第3步起，我不明白事情是怎麼發生的。感謝您的時間

來源

2017-02-01 sandeep pandey

@ daniel-fischer你能幫我解決這個問題嗎 –

這不是你如何通知某人。你可以@用他們的用戶名 –

我不認爲你發佈了正確的字符串。問號字符串中沒有字母O，所以C不能正確。 – 4castle

很多次在選擇題中有錯別字。它在這裏沒有相同的O. 唯一的樹不能通過郵政訂單來繪製回答我們必須搜索一個可能的預訂它可以是如下（ABDECF），所以ANS爲C（假設選項，在錯字），因爲A是最後的職務序列所以它必須是根這樣一個可能的樹是

你知道後A是我們只剩下DEBFC的根源。這裏的一些節點屬於二叉樹的左側，一些屬於右側。左側有多少個節點，右側有多少個節點。由於二叉樹的左側被認爲是第一個，並且由於每個節點最多有兩個孩子，所以DEB將是二叉樹的左側，FC將是右側。現在，我們知道FC在二叉樹的右側。再次，最後一個節點是子樹的根，F是它的左邊。接下來我們來到二叉樹的左邊，它是DEB。再次B將是子樹的根。 D和E分別是它的左側和右側，這樣樹就創建了！

來源

2017-02-01 04:49:47 Akshay

很顯然，A將是根。你在什麼基礎上在左邊和右邊兒童中放置了B，C，可以有其他的方式，對其他人也是如此。DEBFC –

在你知道A是根後，請看編輯的解釋。乾杯 – Akshay

你以什麼爲基礎聲稱「DEB將是二叉樹和FC的左側「因爲所有的DEBFC都可以是左子樹或右子樹。說每個節點最多可以有2個孩子並不妨礙「DEBFC」完全成爲左子樹或右子樹的一部分。 Plz參考http://ugcnetsolved-computerscience.blogspot.in/2012/09/june-2012-paper-ii.html並進入評論部分。 thx –

的一般算法序遍歷去如下，

public void preorder(Node n) { 
    if(n == null) { 
     return; 
    } 
    System.out.println(n.data); 
    preorder(n.left); 
    preorder(n.right); 
}

所以通過序遍歷去時，驗證節點後，做的第一件事是不是空的是打印出來的節點的值。然後繼續遞歸調用該節點的左邊的孩子的方法，然後右邊的孩子。因此，應該很容易看到前三個字母是ABD，因爲預定義方法將在樹的最左側被遞歸地調用。 D沒有孩子，所以前序遍歷可以返回到它在B上的方法調用。現在B的右邊的孩子被訪問，因此現在的順序是ABDE。 E沒有孩子，所以前序遍歷返回B.但是B的所有孩子都被檢查過了，所以現在它回到A.現在前序方法在A的右孩子上被調用。現在的訂單是ABDEC。 C只有一個左邊的孩子，所以在訪問F之後完成前序遍歷，最終的順序是ABDECF。

來源

2017-02-01 05:06:09

如果給定整數很容易創建BT基於更少或更大的屬性。但是，如果我們字母表那麼我憑什麼我們做左節點或右節點

那麼，在Java ("B" > "A") == true因爲字符串是字典順序比較...

的職位上無法搞清楚二叉樹的遍歷階是DEBFCA

通過後序的定義，你知道是根，所以這個問題是B或d是否向左或A的權利（如果你考慮給你的選擇）

也從後期訂購中，您知道D必須是最左邊的元素，因爲它位於後序訂單字符串的開頭。現在您可以排除選項A（D不是C的子項），並且選項B（D不會立即留在A左側）。

在這一點上，你可以決定你的樹看起來像這樣因爲職位的排序中CA結束與D

A 
    B C 
... ... 
D  ......

在後序開始，你有FCA，因此殲將是一個孩子的C，這是A的孩子，要按照這種順序發生。

A 
    B C 
... ... 
D  ... F

我們已經完成了所有，但E.從後序，你有DE，我們有d爲最左側葉，所以E必須是它的兄弟。

這裏是整個樹（F的位置是可以互換的，我認爲）

 A 
    B C 
D E  F

通過淘汰，選項C保持。

來源

2017-02-01 05:10:10

「你知道A是根，所以問題是B或D是否在A的左邊或右邊。」你爲什麼只考慮B或D.爲什麼不使用BF或DE（假設您正在比較給定的預購選項） –

「如果這是一個真正有序的二叉樹，則B在左邊，這排除了選項B.」 - 我不確定他們是否在談論真正有序的二叉樹。如果他們不談論真正有序的二叉樹，會怎麼樣？我知道他們有很多可能性，但我們需要看到預購和後期訂單，並找出哪些預購單與後續訂單一致 –

解決第一條評論。你當然會以A爲根。我想我們在那裏同意。我只考慮B和D，因爲這是你的問題中唯一的選擇。您可以選擇AB或AD。 –

構造給定的二叉樹Post order

回答

相關問題