二叉樹遞歸遍歷存在的問題

如果我們的二叉樹只有左子樹，而且樹的高度還很深的時候，這個時候遞歸調用遍歷的時候，棧幀空間開辟的較大，很可能造成棧溢出。但是我們一個程序中，為堆分配的空間要比棧大的多，這個時候我們可以實現一個二叉樹遍歷的非遞歸的實現形式，模擬棧幀調用的過程，自己模擬一個棧用于保存節點，然后實現遍歷。

非遞歸實現樹的遍歷

前序

首先設置一個指針cur指向根節點，訪問cur然后讓cur入棧，并且是在循環中使cur一直指針它的的左子樹，入棧的時候就訪問了，當我們出棧的時候就使cur指向它的右子樹，這里我們需要兩層循環，一層主要是判斷當前的棧是否為空的，一層主要是判斷一直往左走的時候什么時候到達了左子樹的盡頭了。

    void PrevNoROeder(){stack<Node*> sn;Node* cur = _root;while (cur || !sn.empty()){while (cur){cout << cur->_data << " ";sn.push(cur);cur = cur->_left;}cur = (sn.top())->_right;sn.pop();}cout << endl;}

其實可以這樣子理解的，我們的前序實際上是把所有的問題都轉化成了訪問了左子樹，即使是訪問右子樹的時候，也好像是訪問左子樹一樣，就是把這個樹當成了一個樹根

中序

同樣是上面的內容，這個時候也是可以使用cur內容的，但是這個時候我們不是先訪問，而是先進棧，當我們出棧的時候，我們在訪問，然后出棧，出棧的時候把出來的這個節點的右子樹當成是一個cur，這個時候還是一直當成是一個左子樹來訪問了

void InNoROrder(){stack<Node*> sn;Node* cur = _root;while (cur || !sn.empty()){while (cur){sn.push(cur);cur = cur->_left;}cout << (sn.top())->_data<<" ";cur = (sn.top())->_right;sn.pop();}cout << endl;}

后序

首先讓cur指向的是一個root，然后這個時候讓cur一直往左走，當走到NULL的時候，我們想要出棧但是還不能出棧，因為我們還不知道當前節點的右子樹是不是已經訪問了呢。所以我們加上了一層判斷，就是當我們的當前節點的右子樹不是空的時候，并且當前節點的右子樹不是剛剛出棧的節點的時候，我們就需要把當前節點的右子樹。這里因為需要判斷當前節點的右子樹是不是剛剛出棧的節點，所以我們每次出棧的時候都需要標記一下當前出棧的節點，以便后來的比較使用。如果不是之前訪問的節點，我們就可以出棧訪問了。

void EndNoROrder(){stack<Node*> sn;Node* cur = _root;Node* prev = _root;while (cur || !sn.empty()){if (cur)        //讓所有的左子樹入棧{sn.push(cur);cur = cur->_left;}else        //所有的左子樹都入棧了{if (((sn.top())->_right != NULL) && ((sn.top())->_right != prev)){cur = (sn.top())->_right;}else        //所有的左右子樹都訪問完畢了{cout << (sn.top())->_data<<" ";prev = sn.top();sn.pop();}}}cout << endl;}

通過上面的非遞歸三種方式的比較我們可以發現，三個的一個共同點是，一開始都是讓所有的左子樹節點先入棧，其中先序遍歷的時候，入棧的時候就直接訪問了，中序遍歷的時候是出棧的時候才訪問的，還有一個點就是，出棧的時候讓cur指向棧頂的右子樹，先序遍歷和中序遍歷是直接入棧的，但是后序遍歷是需要一層判斷，就是如果右子樹不是剛剛訪問過的，說明當前右子樹還沒有訪問過，這個時候就需要訪問右子樹，如果是剛剛訪問過的，這個時候就可以直接讓cur出棧訪問就好了，就是我們在后序遍歷的時候，在即將出棧的時候需要加上一層判斷就是當前的右子樹是否已經被訪問過了，如果沒有被訪問過，我們就需要是當前的右子樹入棧如果訪問過了，我們就可以使當前的top出棧了訪問他了

總結

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

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