預訂和與Inorder遍歷的關係

我發現如果我們有Preorder和Inorder Traversal，我們有一棵獨特的樹。預訂和與Inorder遍歷的關係

我可以得出結論：

對於每一根遍歷，我們有多個序遍歷。這是真的還是假的結論？每個人都會幫助我並添加一些細節。

再次感謝。

2014-09-05 user153695

是的，因爲從一個預訂序列中可以創建多個樹。例如：[4,3,1，2]可以被重新定義爲具有根4，子3和2的樹。然後，您可以插入1作爲3的左側或右側子視圖。根據要插入的位置，順序會改變。

你也可以這樣推理：你有n數字，他們可以得到n！排列。如果排列的數量等於可以使用這些數字創建的樹的數量，則可以從遍歷生成樹。事實並非如此，但正如你可以創建許多樹，每個節點只有一個左邊的孩子或者只有一個正確的孩子，這會給你2 * n！而且還有更多，所以必須有一個排列可以產生多於一棵樹=>多於一次的遍歷。

這在一般情況下當然是正確的，BST具有唯一的順序序列。

來源

2014-09-05 06:23:15

所以我們可以說，一個預購是對應一個訂單是假的？ – user153695 2014-09-05 06:26:21

一般情況下，是的。如果我們正在討論BST，那麼1個前序就相當於1箇中序。 – 2014-09-05 06:30:46

非常感謝...添加+投票了。 – user153695 2014-09-05 06:36:02

真，例如：給出的前序遍歷 ABDEC

 a 
    /\ 
    b c 
/\ 
    d e

許多序遍歷是可能的： baedc， dbeac 等等...

來源

2014-09-05 06:27:06 Vishal

預訂和與Inorder遍歷的關係

回答

相關問題