後序遍歷，而無需使用遞歸或堆棧

Question

可能重複：
Post order traversal of binary tree without recursion

我正在經歷中序遍歷算法二叉樹莫里斯。 有人可以請建議是否有一種方法來遍歷postorder而不使用遞歸和堆棧？

Answer 1

你可以用threaded tree來做到這一點。這裏的方法的概要（從here —採取見幻燈片31）：

• 後序：創建一個虛節點，其具有根左後代。
• 變量可以用來檢查當前動作的類型。
• 如果行爲是左遍歷的，並且當前節點有左後代，則遍歷 後裔。否則，行動改爲正確的遍歷。
• 如果動作是正確的遍歷，並且當前節點有一個左子節點，則動作將 更改爲左遍歷。否則，操作變爲訪問節點。
• 如果操作正在訪問節點：訪問當前節點，之後必須找到其後繼訂單 。
• 如果當前節點的父節點通過線程可訪問（即當前節點是父節點的父節點 左邊的子節點），則遍歷設置爲繼續以父節點的右後節。
• 如果當前節點沒有權利後裔，這是節點的右擴展鏈 的末尾。
• 第一：鏈的開始是通過當前節點的線程到達的。
• 第二：鏈中節點的正確引用是相反的。
• 最後：鏈向後掃描時，被訪問的每個節點，則右邊的引用是 恢復到先前的設置。

正如上面的參考文獻所示，如果對樹結構使用臨時修改，也可以在沒有線程的情況下完成。