如何實現BST inorder遍歷？

實際上我想知道的不是如何實現BST的按順序遍歷算法，而是僅僅使用BST的插入，刪除和預序遍歷算法來實現它。
您可以假設您已經獲得了用於插入，刪除和預序遍歷的標準BST算法的實現。如何實現BST inorder遍歷？

你有沒有搜索過？看看這個[鏈接]（http://en.wikipedia.org/wiki/Tree_traversal） – devsaw

嗯......比方說，我們在根節點有+，在左節點有1，在右節點有2。預訂將是+ 1 2，順序將是1 + 2 ..不同之處在於第1和第2個已交換，所以如果您有插入和刪除，您可以遞歸交換每個根節點值與其左節點值，然後使用pre順序遍歷將返回的樹會導致一個inorder遍歷。

我不確定這是否要走，但我希望它能幫上忙。

2011-10-18 05:46:45 Ankur

Ankur，似乎你在某個地方出了問題。我們可以刪除並插入一個元素，但它不會交換這兩個元素，因爲所有的插入和刪除操作都會發生，以保護二進制搜索屬性。 –

我想我找到了解決方案。 :)

我們有預先遍歷，插入和刪除的方法。

假設我們有一個BST。

我們所做的是，我們提供預定義遍歷方法與給定的BST。由於預遍遍歷總是首先到達父節點，因此我們刪除並遞歸地插入每個根（因爲根是第一個父節點）節點，直到根的左子樹爲空。

現在您開始刪除根節點，直到沒有節點爲止。將這些刪除的節點放入數組或任何您想要的位置。你將得到有序的一組節點。（即節點將按照排序順序刪除。最小的第一個等...）

2011-10-21 06:54:39

回答