預購，訂購，以及郵購樹遍歷

Question

我很困惑在訂單，預購和後序遍歷，特別是 這一個，預購：ABAB，郵購：BABA，訂單：AABB 。

我知道根是Pre和Post的第一個也是最後一個元素，但我不明白如何完成二叉樹的構建。

Answer 1

你的文章含糊不清，但沒有多大意義，但我會解釋，前，後順序和爲你構建一個二叉樹。

你的問題沒有意義的原因之一是你沒有建立你訂購的元素的順序，ABAB BABA和AABB意味着沒有任何東西可以正確顯示每個元素的位置（並且每個元素都是一個字母？爲什麼它們會重複）

爲什麼您的問題沒有意義的另一個原因是，您似乎認爲pre，pos和創建二叉樹有關，它們別。

Pre ordering，In Ordering和Post Ordering是所有類型的Depth First Search算法tree traversal。也就是說，它們是導航樹的方式，而不是創建樹。您可以使用這些算法來查找元素，或者只是打印出樹的所有內容，這對於僅通過pointers（如相當於說，array based binary heap）鏈接的樹來說是特別有用的。

想象一下下面的二叉樹（同樣爲所有的例子）

 A 
    B C 
    D E F G 

前序遍歷是一種樹的遍歷算法，其中你總是首先採取的最左邊的路徑。當你不能走得更遠時，你將採取下一個最左邊的路徑，並在下一個節點上遞歸地做同樣的事情。在上面的示例樹中，預置遍歷將從根開始，（A）向左（A，B）再向左（D）不能向左離開，然後向右（E），最後你會結束以下遍歷序列：A B D E C F G

爲了遍歷類似於預遍歷，而不是在每一步顯示，爲了遍歷去最深的左邊它可以去，然後顯示，如果它可以再深入一點，它就會恢復，顯示（因此'按順序'），然後遞歸地嘗試同樣的事情，直到它完成。在樹的例子中，我們實際上首先打印D，返回到B，然後打印B，然後E，然後返回到A，依此類推，因此最終輸出將是D B E A F G C。注意Wikipedias示例可能更有意義，因爲它更復雜。

在後續步驟中，我們從下向上打印，我們在左側子樹中找到最深的節點，並遞歸地打印最深的節點，直到完成，轉到右側子樹並最終打印出根：D E B F G C A。再次，這個例子使用維基百科更有意義，因爲它們有更復雜的樹。

如果你想構建一棵樹，有很多方法可以這樣做，但它完全取決於你想要什麼樣的排序結構。你想要一個二元結構或n元結構嗎？你關心哪個元素在頂部，或者你只想要最小/最大值（如pairing heap或二元堆priority queue）？你有沒有搜索條件，使得樹的每個部分的根必須相對於孩子或他們的父母更大/更小/其他條件？（如binary search tree）

This post如果這不足以解釋遍歷，它也解釋了爲什麼您需要不同類型的排序才能從具有適當連接的節點序列構造樹（如果您的原意是複製二叉樹結構）