// 前序遍歷
void BT_PreOrder(BiTreePtr pNode){ 
if (!pNode)  return;    
visit(pNode);   
BT_PreOrder(pNode->left); 
BT_PreOrder(pNode->right);   }
// 中序遍歷
void BT_PreOrder(BiTreePtr pNode){  
if (!pNode)  return;     
BT_PreOrder(pNode->left);   
visit(pNode);   
BT_PreOrder(pNode->right);}
// 后序遍歷void BT_PreOrder(BiTreePtr pNode){    
if (!pNode)  return;       
BT_PreOrder(pNode->left);   
BT_PreOrder(pNode->right);    
visit(pNode);}

2. 前序遍歷（非遞歸實(shí)現(xiàn)）

復(fù)制代碼代碼如下:

// 用棧實(shí)現(xiàn)
void BT_PreOrderNoRec1(BiTreePtr pNode){ 
stack<BiTreePtr> s; 
while (!pNode || !s.empty())  
{       
if (!pNode)  
{            
visit(pNode);    
s.push(pNode);        
pNode = pNode->left;   
}       
else       
{           
pNode = s.pop(); 
pNode = pNode->right;     
}  
}
}
// 用棧實(shí)現(xiàn)
void BT_PreOrderNoRec2(BiTreePtr pNode){
if (!pNode)   
{       
stack<BiTreePtr> s;  
s.push(pNode);      
while (!s.empty())   
{           
BiTreePtr pvNode = s.pop(); 
visit(pvNode);          
s.push(pvNode->right);       
s.push(pvNode->left);   
}   
}}
// 
不用棧實(shí)現(xiàn) 每個(gè)節(jié)點(diǎn)含父節(jié)點(diǎn)指針和isVisited【默認(rèn)為false】狀態(tài)變量 且該二叉樹含一個(gè)頭節(jié)點(diǎn)
void BT_PreOrderNoRec3(BiTreePtr pNode){    
while (!pNode)
// 回溯到指向根節(jié)點(diǎn)的頭節(jié)點(diǎn)時(shí)退出  
{        
if( !pNode->bVisited )
// 判定是否已被訪問    
{              
visit(pNode);    
pNode->isVisited = true;   
}        
if ( pNode->left && !pNode->left->isVisited )     
pNode = pNode->left;      
else if( pNode->right && !pNode->right->isVisited )  
pNode = pNode->right;       
else   
//回溯     
pNode = pNode->parent;  
}}

3. 中序遍歷（非遞歸實(shí)現(xiàn)）

復(fù)制代碼代碼如下:

// 用棧實(shí)現(xiàn)
void BT_InOrderNoRec1(BiTreePtr pNode){
stack<BiTreePtr> s; 
while (!pNode || !s.empty())   
{       
if (!pNode)       
{          
s.push(pNode);       
pNode = pNode->left;    
}   
else   
{        
pNode = s.pop();  
visit(pNode);       
pNode = pNode->right; 
}  
}}
// 不用棧實(shí)現(xiàn) 每個(gè)節(jié)點(diǎn)含父節(jié)點(diǎn)指針和isVisited【默認(rèn)為false】的狀態(tài)變量 且該二叉樹含一個(gè)頭節(jié)點(diǎn)
void BT_InOrderNoRec2(BiTreePtr pNode){    
while (!pNode) 
// 回溯到指向根節(jié)點(diǎn)的頭節(jié)點(diǎn)時(shí)退出 
{      
while (pNode->left && !pNode->left->isVisited)       
pNode = pNode->left;      
if (!pNode->isVisited)       
{          
visit(pNode);    
pNode->isVisited=true;   
}      
if (pNode->right && !pNode->right->isVisited)  
pNode = pNode->right;   
else          
pNode = pNode->parent; 
}}

4. 后序遍歷（非遞歸實(shí)現(xiàn)）

復(fù)制代碼代碼如下:

void BT_PostOrderNoRec(BiTreePtr pNode){ 
if(!pNode) return; 
stack<BiTreePtr> s;
s.push(pNode);  
while (!s.empty())   
{     
BiTreePtr pvNode = s.pop();  
if (pvNode->isPushed)
// 表示其左右子樹都已入棧，訪問該節(jié)點(diǎn)       
visit(pvNode);    
else     
{        
if (pvNode->right)  
{              
pvNode->right->isPushed = false;
S.push(pvNode->right);          
}           
if (pvNode->left)     
{               
pvNode->left->isPushed = false;   
s.push(pvNode->left);          
}          
pvNode->isPushed = true;      
s.push(pvNode);    
}   
}}

5. 層序遍歷（使用隊(duì)列）

復(fù)制代碼代碼如下:

void BT_LevelOrder(BiTreePtr pNode){ 
if (!pNode) return;   
queue<BiTreePtr> q;   
q.push(pNode);  
BiTreePtr pvNode;
while (!q.empty()) 
{      
pvNode = q.pop();     
visit(pvNode);   
if (pvNode->left) 
q.push(pvNode->left);  
if (pvNode->right)    
q.push(pvNode->right);   
}}