BST從預訂中按照相同順序插入節點

要從給定的預遍歷構造BST，如果我嘗試按照與預先給定的順序相同的順序插入到BST中，我會得到BST。那麼，我們不要通過排序元素或執行任何其他算法來創建按序？BST從預訂中按照相同順序插入節點

有沒有一個例子表明樹不能通過插入元素來構造？

2013-10-28 Gaurav

如果不能通過向其中插入元素來構建一棵樹，還有什麼可能？ –

我的意思是我不需要使用任何算法，我們只需要按照與預先訂單相同的順序插入它們。 – Gaurav

我有同樣的疑問。爲什麼有兩個問題需要預先訂購和訂購，而只能預購？ – user1422163

你是對的......你可以按照預先遍歷的順序插入節點來重建樹。

插入的第一個節點必須放置在正確的位置，因爲它是根，並且前序遍歷總是首先放置根。在前序遍歷中的後面是左子樹的前序佈局，然後是右子樹。隨着左側子樹節點的插入，它們將從根部向左插入，然後遞歸地在該子樹上應用相同的過程。正確的子樹以相同的方式重建。使用歸納法，如果你喜歡，你可以正式證明這一點。

希望這會有所幫助！

2013-10-28 16:54:10 templatetypedef

回答