1 二叉樹的遍歷

1.1 前序遍歷

對于每棵子樹，先處理根，然后處理左子樹，最后處理右子樹。根最先訪問，所以是前序遍歷。

1.2 中序遍歷

對于每棵子樹，先處理左子樹，然后處理根，最后處理右子樹。根中間訪問，所以是中序遍歷。

1.3 后序遍歷

對于每棵子樹，先處理左子樹，然后處理右子樹，最后處理根。根最后訪問，所以是后序遍歷。

2 二叉樹的中序遍歷的非遞歸實現

第一，用棧實現；

第二，每個元素都要入棧；

第三，每當有新的元素入棧了，都要檢查棧頂元素是不是可以出棧了。

第四，可以出棧的條件：

??????? 1， 它的左兒子為NULL

??????? 2， 剛進行了一次出棧操作，現在它是新的棧頂元素，這個時候就證明它的左子樹已經被訪問完了，現在輪到它了。

3 二叉樹的后序遍歷的非遞歸實現

入棧：

第一，root無條件入棧

第二，latest_poped為NULL時，左孩子不為null，左孩子入棧；左孩子為null，右孩子不為null，右孩子入棧；

第三，latest_poped不為null時：

??????? latest_poped是左孩子時，右孩子不為null，右孩子入棧；

??????? latest_poped不是孩子時，左孩子不為null，左孩子入棧；左孩子為null，右孩子不為null，右孩子入棧；

出棧：

第一，葉子出棧

第二，latest_poped是右孩子時，出棧

第三，latest_poped是左孩子，并且右孩子為null，出棧。

?

轉載于:https://www.cnblogs.com/hustdc/p/7767883.html

總結

以上是生活随笔為你收集整理的二叉树前序、中序和后序遍历的非递归实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。