注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

饥民2011

一直在搬砖

 
 
 

日志

 
 
 
 

数据结构 二叉树的遍历  

2013-05-04 22:07:22|  分类: Data structure |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
所谓遍历, 无非就是把1个容器的所有元素逐个输出, 而这个输出是线性的。

   但是二叉树是1个非线性的容器,  如何把它的元素按一定顺序输出就是1个值得学习的课题了。

   一般来讲, 遍历二叉树有3种方法, 先序遍历, 中序遍历以及后续遍历。 无论哪一种方法都可以把二叉树里的元素线性输出。但是无论哪种方法,都无法根据输出后的线性元素还原成正确的二叉树结构, 除非先把这棵二叉树转化为完全二叉树(添加不存放实际数据的空节点)。





二叉树先序遍历的定义:

       定义很简单, 无非3个步骤:

       第一步: 先访问二叉树的根节点

       第二步: 先序遍历左子树

       第三步 :  先序遍历右子树   



       我们来看看上面先序遍历的定义, 里面的步骤居然也用到了先序遍历这个动作, 有经验的读者也许发现这就是递归了。



二叉树先序遍历的伪算法:

       我们来假设先序遍历这个函数是f(Tree * A);   其中A是二叉树树类型的指针

       那么f(Tree A)可以利用递归来定义:

 

  1. f(Tree * A){  
  2.         printf(A->root);    //root是Tree类型的一个成员,表示根节点  
  3.   
  4.         if (NULL != A->LeftTree()){  //LeftTree 是Tree的一个成员,返回Tree的左子树的指针(也是Tree类型指针)   
  5.                 f(A->LeftTree());  
  6.         }   
  7.   
  8.         if (NULL != A->RightTree()){  //RightTree 是Tree的一个成员,返回Tree的右子树的指针(也是Tree类型指针)  
  9.                 f(A->RightTree());  
  10.         }  
  11. }  

      见到这个函数会不断地调用自己, 直到左子树和右子树都为空(叶子节点), 才会遇到出口。


如下图:





二叉树中序遍历的定义:

       二叉树的中序遍历其实跟先序遍历很类似, 都是利用递归来实现的, 但是中序遍历执行步骤有些不同。

       中序遍历也分3个步骤:

       第一步: 中序遍历左子树

       第二步: 访问根节点

       第三步 :  中序遍历右子树


      

       可以看出,跟先序遍历的差别无非就是先遍历左子树和先访问根节点的区别。




二叉树中序遍历的伪算法:

       假设中序遍历这个函数是g(Tree * A);   其中A是二叉树树类型的指针

       那么g(Tree A)可以利用递归来定义:

  1. g(Tree * A){  
  2.         if (NULL != A->LeftTree()){  //LeftTree 是Tree的一个成员,返回Tree的左子树的指针(也是Tree类型指针)   
  3.                 g(A->LeftTree());  
  4.         }   
  5.   
  6.         printf(A->root);    //root是Tree类型的一个成员,表示根节点  
  7.   
  8.         if (NULL != A->RightTree()){  //RightTree 是Tree的一个成员,返回Tree的右子树的指针(也是Tree类型指针)  
  9.                 g(A->RightTree());  
  10.         }  
  11. }  

如下图:


注意与先序遍历的细节区别啊~



二叉树后序遍历的定义:

       理解了先序和中序遍历后, 后序遍历也不难理解, 都是一个原理的啊。

       后序遍历的3个步骤:

       第一步: 后序遍历左子树

       第二步: 后序遍历右子树

       第三步 :  访问根节点


       可以见到, 左子树和右子树的顺序不变, 只不过根节点的顺序留到最后了。


      

二叉树后序遍历的伪算法:

       假设后序遍历这个函数是k(Tree * A);   其中A是二叉树树类型的指针

       那么k(Tree A)可以利用递归来定义:

  1. k(Tree * A){  
  2.         if (NULL != A->LeftTree()){  //LeftTree 是Tree的一个成员,返回Tree的左子树的指针(也是Tree类型指针)   
  3.                 k(A->LeftTree());  
  4.         }   
  5.   
  6.         if (NULL != A->RightTree()){  //RightTree 是Tree的一个成员,返回Tree的右子树的指针(也是Tree类型指针)  
  7.                 k(A->RightTree());  
  8.         }  
  9.   
  10.         printf(A->root);    //root是Tree类型的一个成员,表示根节点  
  11. }  


如下图:







  评论这张
 
阅读(227)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017