二叉樹的遍歷可以使用遞歸的方式實現(xiàn)，并且代碼非常簡單。而遞歸實際就是函數(shù)反復(fù)的調(diào)用本身，在棧上反復(fù)壓棧。所以我們可以用棧來模擬實現(xiàn)遞歸。
1.前序遍歷
（1）棧是后進先出的特點，所以無條件的把棧的根節(jié)點入棧，在把棧頂元素輸出之后依次把右孩子，左孩子壓入棧中。
代碼如下：
重慶分公司
重慶分公司
void _PrevOrder(Node * root)
{
stack s;
if (root == NULL)
{
return;
}
s.push(root);//將第一個元素入棧
while (!s.empty())//當棧不為空時
{
root = s.top();
cout << root->_data << "->";//打印節(jié)點
s.pop();
//棧的特點，后進先出，所以，先壓右子樹
if (root->_right)//遍歷右子樹
{
s.push(root->_right);
}
if (root->_left)//遍歷左子樹
{
s.push(root->_left);
}
}
} 2.中序遍歷
（1）一直入棧，一直到二叉樹的最左邊最下邊的節(jié)點。
（2）按照中序遍歷的特點：左子樹->根節(jié)點->右子樹，輸出棧頂?shù)脑?，并且彈出，必須保留該?jié)點的指針。
（3）此時，該判斷此節(jié)點的右子樹：
a.右子樹為NULL，返回到棧頂；
b.右子樹不為NULL，把該節(jié)點當根節(jié)點，重復(fù)（1）（2）（3）......
代碼如下：
void _InOrder(Node * root)
{
if (root == NULL)
{
return;
}
Node * cur = root;
stack s;
while (cur || !s.empty())
{
while (cur)//當沒有左子樹時，停止入棧
{
s.push(cur);
cur = cur->_left;
}
Node * top = s.top();//保留棧頂指針，判斷是否有右子樹
cout << top->_data << "->";
s.pop();
if (top->_right == NULL)//沒有右子樹時，不需要壓棧
{
cur = NULL;
}
else//當存在右子樹時，把右子樹的根節(jié)點壓入棧中，循環(huán)去判斷該節(jié)點的左子樹是否存在
{
cur = top->_right;
}
}
} 3.后序遍歷
（1）一直入棧，一直到二叉樹的最左邊最下邊的節(jié)點。
（2）按照后序遍歷的特點：左子樹->右子樹->根節(jié)點，輸出棧頂?shù)脑兀⑶覐棾?，必須保留該?jié)點的指針。
（3）此時，該判斷此節(jié)點的右子樹，如果存在右子樹，把該節(jié)點當作根節(jié)點，重復(fù)（1）（2）（3）
代碼如下：
void _PostOrder(Node * root)
{
if (root == NULL)
{
return;
}
Node * cur = root;
Node * prev = NULL;
stack s;
while (cur || !s.empty())
{
while (cur)//當沒有左子樹時，停止入棧
{
s.push(cur);
cur = cur->_left;
}
Node * top = s.top();//保留棧頂指針，判斷它的右子樹是否為空或者已經(jīng)出棧
if (top->_right == NULL || top->_right == prev)
{
cout << top->_data << "->";
s.pop();
prev = top;//保留出棧元素的指針
cur = NULL;
}
else//當存在右子樹時，把右子樹的根節(jié)點壓入棧中，循環(huán)去判斷該節(jié)點的左子樹是否存在
{
cur = top->_right;
}
}
} 另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國服務(wù)器、虛擬主機、免備案服務(wù)器”等云主機租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務(wù)可用性高、性價比高”等特點與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場景需求。
