一：前中後序遞歸實現
[cpp]
/*
前中後序的遞歸實現理解起來最為簡單，要點在於visit(node)的位置。
*/
/*
前中後序遞歸實現
*/
//前序遍歷
void BT_PreOrder(BitTree node)
{
if(!node) return;
visit(node);
BT_PreOrder(node->left);
BT_PreOrder(node->right);
}
//中序遍歷
void BT_InOrder(BitTree node)
{
if(!node) return;
BT_PreOrder(node->left);
visit(node);
BT_PreOrder(node->right);
}
//中序遍歷
void BT_PostOrder(BitTree node)
{
if(!node) return;
BT_PreOrder(node->left);
BT_PreOrder(node->right);
visit(node);
}
/*
前中後序的遞歸實現理解起來最為簡單，要點在於visit(node)的位置。
*/
/*
前中後序遞歸實現
*/
//前序遍歷
void BT_PreOrder(BitTree node)
{
if(!node) return;
visit(node);
BT_PreOrder(node->left);
BT_PreOrder(node->right);
}
//中序遍歷
void BT_InOrder(BitTree node)
{
if(!node) return;
BT_PreOrder(node->left);
visit(node);
BT_PreOrder(node->right);
}
//中序遍歷
void BT_PostOrder(BitTree node)
{
if(!node) return;
BT_PreOrder(node->left);
BT_PreOrder(node->right);
visit(node);
}
二：層序遞歸實現
[cpp]
*
層序遍歷
這種方式用隊列來實現，也是最容易理解的方式，思路如下：
按照層序遍歷的定義，訪問完當前節點之後，則當前節點的左子節點具備了倒數第二優先級，當前節點的右子節點具備了倒數第一優先級，利用隊列先進先出的特性（可以確定最低的優先級），可以實現。
*/
void BT_LevelOrder(BitTree node)
{
if(!node) return;
queue<BitTree> q;
q.push(node);
BitTree pvNode;
while(!q.empty())
{
pvNode = q.pop();
visit(pvNode);
if(!pvNode->left) q.push(pvNode->left);
if(!pvNode->right) q.push(pvNode->right);
}
}
/*
層序遍歷
這種方式用隊列來實現，也是最容易理解的方式，思路如下：
按照層序遍歷的定義，訪問完當前節點之後，則當前節點的左子節點具備了倒數第二優先級，當前節點的右子節點具備了倒數第一優先級，利用隊列先進先出的特性（可以確定最低的優先級），可以實現。
*/
void BT_LevelOrder(BitTree node)
{
if(!node) return;
queue<BitTree> q;
q.push(node);
BitTree pvNode;
while(!q.empty())
{
pvNode = q.pop();
visit(pvNode);
if(!pvNode->left) q.push(pvNode->left);
if(!pvNode->right) q.push(pvNode->right);
}
}
三：前序非遞歸實現
[cpp]
/*
前序遍歷非遞歸實現1
這種方式用棧來實現，也是最容易理解的方式，思路如下：
按照前序遍歷的定義，訪問完當前節點之後，則當前節點的左子節點具備了第一優先級，當前節點的右子節點具備了第二優先級，
利用棧後進先出的特性（可以確定最高的優先級），可以實現。
*/
void BT_PreOrderNoRec(BitTree node)
{
if(!node) return;
stack<BitTree> s;
BitTree pvNode;
s.push(node);
while(!s.empty())
{
pvNode = s.pop();
visit(pvNode);
if(!pvNode->right) s.push(pvNode->right);
if(!pvNode->left) s.push(pvNode->left);
}
}
/*
前序遍歷非遞歸實現2
在網上看到的一種寫法，個人覺得不如第一種實現起來更易懂
*/
void BT_PreOrderNoRec2(BitTree node)
{
if(!node) return;
stack<BitTree> s;
while(!node && !s.empty())
{
/*如果當前節點不為空，則直接訪問，然後將節點存儲到棧中（僅僅用來將來尋找右子節點），然後當前節點變為左字節點*/
if(node)
{
visit(node);
s.push(node);
node = node->left;
}
/*如果當前節點為空，則到棧中取出上一個節點，並找出右子節點進行訪問*/
else
{
node = s.pop();
node = s.right;
}
}
}
/*
前序遍歷非遞歸實現1
這種方式用棧來實現，也是最容易理解的方式，思路如下：
按照前序遍歷的定義，訪問完當前節點之後，則當前節點的左子節點具備了第一優先級，當前節點的右子節點具備了第二優先級，
利用棧後進先出的特性（可以確定最高的優先級），可以實現。
*/
void BT_PreOrderNoRec(BitTree node)
{
if(!node) return;
stack<BitTree> s;
BitTree pvNode;
s.push(node);
while(!s.empty())
{
pvNode = s.pop();
visit(pvNode);
if(!pvNode->right) s.push(pvNode->right);
if(!pvNode->left) s.push(pvNode->left);
}
}
/*
前序遍歷非遞歸實現2
在網上看到的一種寫法，個人覺得不如第一種實現起來更易懂
*/
void BT_PreOrderNoRec2(BitTree node)
{
if(!node) return;
stack<BitTree> s;
while(!node && !s.empty())
{
/*如果當前節點不為空，則直接訪問，然後將節點存儲到棧中（僅僅用來將來尋找右子節點），然後當前節點變為左字節點*/
if(node)
{
visit(node);
s.push(node);
node = node->left;
}
/*如果當前節點為空，則到棧中取出上一個節點，並找出右子節點進行訪問*/
else
{
node = s.pop();
node = s.right;
}
}
}
四：中序非遞歸
[cpp]
/*
中序遍歷非遞歸實現
用棧來實現，這種方式可以用遞歸的思路來理解
*/
void BT_InOrderNoRec(BitTree node)
{
if(!node) return;
stack<BitTree> s;
while(!s.empty())
{
/*如果當前節點不為空，則不訪問，而是將它放入棧中，然後當前節點變為左字節點；
一直采取這種方式，根據棧先進後出的特點，將來訪問的時候左字節點在前，當前節點在後；
正好是中序遍歷的特性
*/
if(!node)
{
push(node);
node = node->left();
}
/*如果當前節點為空，則去棧裡取出節點訪問，然後訪問右子節點。
這裡有些不好理解，其實這裡的開端是左字節點為空了，所以訪問了當前節點，然後右子節點；
同時當前節點為根的二叉樹其實是上層的左字節點，依次類推正好是中序遍歷的特性
*/
else
{
node = s.pop();
visit(node);
node = node->right;
}
}
}
/*
中序遍歷非遞歸實現
用棧來實現，這種方式可以用遞歸的思路來理解
*/
void BT_InOrderNoRec(BitTree node)
{
if(!node) return;
stack<BitTree> s;
while(!s.empty())
{
/*如果當前節點不為空，則不訪問，而是將它放入棧中，然後當前節點變為左字節點；
一直采取這種方式，根據棧先進後出的特點，將來訪問的時候左字節點在前，當前節點在後；
正好是中序遍歷的特性
*/
if(!node)
{
push(node);
node = node->left();
}
/*如果當前節點為空，則去棧裡取出節點訪問，然後訪問右子節點。
這裡有些不好理解，其實這裡的開端是左字節點為空了，所以訪問了當前節點，然後右子節點；
同時當前節點為根的二叉樹其實是上層的左字節點，依次類推正好是中序遍歷的特性
*/
else
{
node = s.pop();
visit(node);
node = node->right;
}
}
}
五：後序非遞歸
[cpp]
/*
後序遍歷非遞歸實現
用棧來實現，不是很好理解，但是起碼不用借助各種標志位
思路如注釋所寫
*/
void BT_PostOrderNoRec(BitTree node)
{
if(!node) return;
stack<BitTree> s;
BitTree tmp;//用來標志剛剛訪問過的節點
while(!node && !s.empty())
{
//如果當前節點不為空，則壓入棧，當前節點變為左字節點
if(node)
{
s.push(node);
node = node->left;
}
//如果為空，則需要根據棧頂的節點來判定下一步
else
{
//獲取棧頂節點,不是pop
node = s.getPop();
//如果棧頂節點有右子節點，並且（這不好理解，但很重要）右子節點不是我們剛剛訪問過的，
//則，我們要去右子樹訪問
if(node->right && node->right != tmp)
{
//把右子樹當作一個新的開始進行訪問：根節點壓入棧，訪問左字節點
s.push(node->right);
node = node->right->left;
}
//如果棧頂節點沒有右子節點，或者我們剛剛訪問過右子節點，則達到後序遍歷的要求，我們可以訪問當前節點
else
{
//訪問當前節點，設置標志節點(tmp)為當前節點，當前節點置為空
node = s.pop();
visit(node);
tmp = node;
node = null;
}
}
}
}
/*
後序遍歷非遞歸實現
用棧來實現，不是很好理解，但是起碼不用借助各種標志位
思路如注釋所寫
*/
void BT_PostOrderNoRec(BitTree node)
{
if(!node) return;
stack<BitTree> s;
BitTree tmp;//用來標志剛剛訪問過的節點
while(!node && !s.empty())
{
//如果當前節點不為空，則壓入棧，當前節點變為左字節點
if(node)
{
s.push(node);
node = node->left;
}
//如果為空，則需要根據棧頂的節點來判定下一步
else
{
//獲取棧頂節點,不是pop
node = s.getPop();
//如果棧頂節點有右子節點，並且（這不好理解，但很重要）右子節點不是我們剛剛訪問過的，
//則，我們要去右子樹訪問
if(node->right && node->right != tmp)
{
//把右子樹當作一個新的開始進行訪問：根節點壓入棧，訪問左字節點
s.push(node->right);
node = node->right->left;
}
//如果棧頂節點沒有右子節點，或者我們剛剛訪問過右子節點，則達到後序遍歷的要求，我們可以訪問當前節點
else
{
//訪問當前節點，設置標志節點(tmp)為當前節點，當前節點置為空
node = s.pop();
visit(node);
tmp = node;
node = null;
}
}
}
}
