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

2016-02-19 11:02 36 1 收藏

生活已是百般艰难,为何不努力一点。下面图老师就给大家分享c++二叉树的几种遍历算法,希望可以让热爱学习的朋友们体会到设计的小小的乐趣。

【 tulaoshi.com - 编程语言 】

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){
stackBiTreePtr 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)  
{      
stackBiTreePtr s; 
s.push(pNode);     
while (!s.empty())  
{          
BiTreePtr pvNode = s.pop();
visit(pvNode);         
s.push(pvNode-right);      
s.push(pvNode-left);  
}  
}}
//
不用栈实现 每个节点含父节点指针和isVisited状态变量 且该二叉树含一个头节点
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){
stackBiTreePtr s;
while (!pNode || !s.empty())  
{      
if (!pNode)      
{         
s.push(pNode);      
pNode = pNode-left;   
}  
else  
{       
pNode = s.pop(); 
visit(pNode);      
pNode = pNode-right;

}}
// 不用栈实现 每个节点含父节点指针和isVisited的状态变量 且该二叉树含一个头节点
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;
stackBiTreePtr 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);   
}  
}}

(本文来源于图老师网站,更多请访问http://www.tulaoshi.com/bianchengyuyan/)

5. 层序遍历(使用队列)
代码如下:

void BT_LevelOrder(BiTreePtr pNode){
if (!pNode) return;  
queueBiTreePtr 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);  
}}

(本文来源于图老师网站,更多请访问http://www.tulaoshi.com/bianchengyuyan/)

来源:http://www.tulaoshi.com/n/20160219/1596406.html

延伸阅读
Word-BREAK: break-all; PADDING-TOP: 4px; BORDER-BOTTOM: windowtext 0.5pt solid">#include stdio.h #include stdlib.h #define STACK_MAX_SIZE 30 #define QUEUE_MAX_SIZE 30 #ifndef elemType  typedef char elemType; #endif /***********************************************************************...
根据前序和中序序列生成二叉树 作者:宋科 作者主页:kesongemini.diy.163.com 下载本文示例代码 一、前言: 我的一个同事拿来她老公的远程教育的考试题,叫大家帮着做,我写了这道,源码通过VC6编译链接,执行成功,呵呵;)题目就是给出了一个二叉树的前序序列(ABDCEGF)和中序序列(...
clone模式在平衡排序二叉树实现中的应用 作者:wujinglong 下载本文示例源代码 clone模式既prototype模式,是构造模式中的一种。其意图为:用原型实例指定创建对象的种类,并且通过拷贝这些原型创建新的对象。 关键代码如下: virtual product * prototype::clone(){return new p...
一棵二叉查找树是按二叉树结构来组织的。这样的树可以用链表结构表示,其中每一个结点都是一个对象。结点中除了数据外,还包括域left,right和p,它们分别指向结点的左儿子、右儿子,如果结点不存在,则为NULL。 它或者是一棵空树;或者是具有下列性质的二叉树: 1)若左子树不空,则左子树上所有结点的值均小于它的根结点的值; (2)若右子树...
本课主题: 实验七 查找 教学目的: 练习顺序查找、折半查找及二叉排序树的实现 教学重点: 教学难点: 授课内容: 顺序查找 折半查找 顺序查找及折半查找示例 二叉排序树 示例

经验教程

967

收藏

46
微博分享 QQ分享 QQ空间 手机页面 收藏网站 回到头部