您的位置：首页 > 编程技术 > C语言  >  c++二叉树的几种遍历算法

c++二叉树的几种遍历算法

 更新时间：2020年4月25日 17:48  点击：1257

1. 前序/中序/后序遍历（递归实现）

复制代码 代码如下:

// 前序遍历
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. 前序遍历（非递归实现）
复制代码 代码如下:

// 用栈实现
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;    
} 
}
}
// 用栈实现
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);  
}  
}}
//
不用栈实现 每个节点含父节点指针和isVisited【默认为false】状态变量 且该二叉树含一个头节点
void BT_PreOrderNoRec3(BiTreePtr pNode){   
while (!pNode)
// 回溯到指向根节点的头节点时退出 
{       
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. 中序遍历（非递归实现）

复制代码 代码如下:

// 用栈实现
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;
} 
}}
// 不用栈实现 每个节点含父节点指针和isVisited【默认为false】的状态变量 且该二叉树含一个头节点
void BT_InOrderNoRec2(BiTreePtr pNode){   
while (!pNode)
// 回溯到指向根节点的头节点时退出
{     
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. 后序遍历（非递归实现）
复制代码 代码如下:

void BT_PostOrderNoRec(BiTreePtr pNode){
if(!pNode) return;
stack<BiTreePtr> s;
s.push(pNode); 
while (!s.empty())  
{    
BiTreePtr pvNode = s.pop(); 
if (pvNode->isPushed)
// 表示其左右子树都已入栈，访问该节点      
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. 层序遍历（使用队列）

复制代码 代码如下:

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);  
}}

[!--infotagslink--]

相关文章

  • JS中的二叉树遍历详解

    这篇文章主要为大家详细介绍了JS中的二叉树遍历，何为二叉树，什么是二叉树的遍历，感兴趣的小伙伴们可以参考一下...2016-03-22

  • 二叉树的遍历算法(详细示例分析)

    以下代码是对二叉树的遍历算法进行了分析介绍，需要的朋友可以参考下...2020-06-25

  • 二叉树遍历 非递归 C++实现代码

    对于二叉树，有前序、中序以及后序三种遍历方法。因为树的定义本身就是递归定义，因此采用递归的方法去实现树的三种遍历不仅容易理解而且代码很简洁。而对于树的遍历若采用非递归的方法，就要采用栈去模拟实现...2020-04-25

  • 二叉树先根（先序）遍历的改进

    这篇文章主要介绍了二叉树先根（先序）遍历的改进，有需要的朋友可以参考一下...2020-04-25

  • php 二叉树遍历算法与例子

    二叉树算法在小编大学时学数据结构时会学到的一个算法了，这个可以在搜索与排序中提高50%的搜索性能了，下面我们来看一些关于php 二叉树遍历算法与例子吧。 二叉树...2016-11-25

  • c++二叉树的几种遍历算法

    c++二叉树的几种遍历算法，需要的朋友可以参考一下...2020-04-25