無遞歸的二叉樹遍歷的直觀解釋

我見過很多文章和書籍（和堆棧溢出的答案），它們展示瞭如何使用顯式堆棧而不是遞歸迭代地執行深度優先樹遍歷的前序，後序和後序。例如：https://en.wikipedia.org/wiki/Tree_traversal#Depth-first_search_2 無遞歸的二叉樹遍歷的直觀解釋

預訂遍歷很簡單，但我認爲其他人很複雜，遠不明顯。

是否有任何源代碼（最好是文章或書籍）直觀地解釋這些算法，所以你可以看到有人會如何想出他們呢？

2016-08-02 gesgsklw

從技術上講，使用堆棧是遞歸，只是不明確。這是隱式遞歸，因爲類似於一遍又一遍地調用一個方法，使用了一個堆棧。這只是一種方式使用調用堆棧而另一種使用節點堆棧。沒有某種遞歸，你無法真正穿過一棵樹。 –

@DaneBrick，*技術*，這是不正確的。它是一個函數根據自身定義的遞歸。 –

@MattTimmermans我明白了，但是如果OP在理解堆棧的樹遍歷時有困難，但是可以理解遞歸的遍歷，那麼我想指出兩種遍歷方法其實都非常相似。因爲堆棧用於遞歸。 –

在所有情況下，堆棧用於存儲您不能馬上完成的工作。預購案例最簡單，因爲只有一種工作需要推遲 - 處理一個子節點。

預訂：堆棧保存要處理的節點。要處理節點，請訪問它，將正確的子節點推入堆棧，然後處理下一個左側子節點。如果沒有剩下的孩子，那麼從堆棧中抓一個。

Inorder也很容易。堆棧具有存儲節點訪問和節點的過程，但過程中的節點總是剛去過，所以一個節點的右子：

中序：堆棧持有節點訪問。當我們從堆棧中取出一個節點時，我們訪問它，然後處理它的正確的孩子。當我們處理一個節點時，我們把它放在堆棧上，然後處理它的左邊的孩子。

後序是棘手的，因爲堆棧具有存儲節點訪問和節點的過程，他們並不總是簡單的相關就像他們在中序情況。堆棧必須以某種方式指示哪個是哪個。

你可以這樣說：

後序：堆棧持有節點訪問或處理，與已處理孩子的號碼。要處理來自堆棧的條目(n,x)，請訪問節點n，如果它有< = x個子項。否則將(n,x+1)放在堆棧上並處理節點的第一個未處理的子節點。

2016-08-02 20:23:33

回答