二叉樹的三種遍歷方式一直都是為人津津樂道的面試題，考察一個人對遞歸的理解讓他寫個三種遍歷方式是最簡單的考察方式了，那麼考察一個人對遞歸的理解更加深層次的方式就是讓他用循環模擬遞歸（就是把遞歸代碼轉換成非遞歸），一般想要實現這樣的東西是需要棧的，或許說使用棧的結構更加貼合函數棧的壓入和彈出，更加好理解
遞歸的三種遍歷方式分別為，前序遍歷，中序遍歷，後序遍歷，在考慮完了遞歸的寫法之後，非遞歸的寫法更加難； 相關閱讀：二叉樹的常見問題及其解決程序 http://www.linuxidc.com/Linux/2013-04/83661.htm
【遞歸】二叉樹的先序建立及遍歷 http://www.linuxidc.com/Linux/2012-12/75608.htm
在JAVA中實現的二叉樹結構 http://www.linuxidc.com/Linux/2008-12/17690.htm
【非遞歸】二叉樹的建立及遍歷 http://www.linuxidc.com/Linux/2012-12/75607.htm
二叉樹遞歸實現與二重指針 http://www.linuxidc.com/Linux/2013-07/87373.htm
二叉樹先序中序非遞歸算法 http://www.linuxidc.com/Linux/2014-06/102935.htm
輕松搞定面試中的二叉樹題目 http://www.linuxidc.com/linux/2014-07/104857.htm
void PreOrder_NonR()
{
if (_root == NULL )
{
return;
}
stack<BinaryTreeNode <T>*> s;
s.push(_root);
while (!s.empty())
{
BinaryTreeNode<T >* top = s.top();
cout << top->_data << " " ;
s.pop();
if (top->_right)
{
s.push(top->_right);
}
if (top->_left)
{
s.push(top->_left);
}
}
cout << endl;
}
中序遍歷可以采用遞歸的思考方式，因為中序遍歷的方式是在訪問完左子樹之後再去訪問根節點，所以在訪問完根節點之後進入右子樹，右子樹又相當於一個新的根節點，所以應該采取訪問完根節點之後將右孩子立刻壓入棧，然後進入循環可以寫出下面的代碼
void InOrder_NonR()
{
stack<BinaryTreeNode <T>*> s;
BinaryTreeNode<T > *cur = _root;
while (cur || !s.empty())
{
while (cur)
{
s.push(cur);
cur = cur->_left;
}
if (!s.empty())
{
BinaryTreeNode<T > *top = s.top();
cout << top->_data << " " ;
s.pop();
cur = top->_right;
}
}
cout << endl;
}
後序遍歷是先訪問左子樹和右子樹，所以當左孩子出棧的時候，下一個棧內節點（即根節點）不能立刻就訪問，需要考慮幾種情況，如果此時此刻右孩子為空，那麼可以訪問，如果此時有孩子不為空，那麼需要考慮右孩子是否被訪問過了，如果訪問過了，則可以訪問根節點，否則需要先訪問右子樹然後再去訪問根節點，可以利用一個變量來保存之前訪問的是哪一個節點，可以寫出如下代碼
void PostOrder_NonR()
{
stack<BinaryTreeNode <T> *> s;
BinaryTreeNode<T >* PreVisited = NULL;
BinaryTreeNode<T >* cur = _root;
while (cur || !s.empty())
{
while (cur)
{
s.push(cur);
cur = cur->_left;
}
BinaryTreeNode<T > *top = s.top();
if (top->_right == NULL || PreVisited == top->_right)
{
cout << top->_data << " " ;
s.pop();
PreVisited = top;
}
else
{
cur = top->_right;
}
}
cout << endl;
}
