woaidongmao

文章均收录自他人博客,但不喜标题前加-[转贴],因其丑陋,见谅!~
随笔 - 1469, 文章 - 0, 评论 - 661, 引用 - 0
数据加载中……

数据结构与算法:树的遍历算法

——此文章摘自《多任务下的数据结构与算法》定价:58 特价:44.7 购买>>clip_image001

    1. 使用递归的遍历算法

    对普通树的遍历只有深度优先、宽度优先两种遍历方法,深度优先又可以分为先序和后序两种,但没有中序遍历之说,中序遍历只有二叉树才有。

    下面分别给出先序遍历、后序遍历和宽度优先遍历的流程如图5-2、图5-3、图5-4所示。

    2.
使用栈的非递归遍历算法

    所有的递归算法都可以通过使用栈操作来变成非递归的算法,本质上讲,递归算法是利用系统本身提供的栈,不过系统本身的栈深度很大时效率非常低,因此可以使用自己的栈来取代系统的栈将递归算法变成非递归算法。

clip_image002
5-2  普通树的先序遍历流程图

 

clip_image003
5-3  普通树的后序遍历流程图

 

clip_image004
5-4  树的宽度方向遍历流程图

 

    3. 不使用栈的非递归遍历算法

    对于普通树来说,也可以设计出不使用栈的非递归遍历算法,不过这要求每个节点都保存它的父节点指针,不使用栈的非递归遍历算法流程如图5-5所示。

clip_image005
5-5  不使用栈的普通树的非递归遍历流程图

 

 

posted on 2010-07-16 22:34 肥仔 阅读(1595) 评论(1)  编辑 收藏 引用 所属分类: 数据结构 & 算法

评论

# re: 数据结构与算法:树的遍历算法  回复  更多评论   

怎么没有了下文了???
2011-07-11 00:14 | 小基

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理