——此文章摘自《多任务下的数据结构与算法》定价:58元 特价:44.7元 购买>>
1. 使用递归的遍历算法
对普通树的遍历只有深度优先、宽度优先两种遍历方法,深度优先又可以分为先序和后序两种,但没有中序遍历之说,中序遍历只有二叉树才有。
下面分别给出先序遍历、后序遍历和宽度优先遍历的流程如图5-2、图5-3、图5-4所示。
2. 使用栈的非递归遍历算法
所有的递归算法都可以通过使用栈操作来变成非递归的算法,本质上讲,递归算法是利用系统本身提供的栈,不过系统本身的栈深度很大时效率非常低,因此可以使用自己的栈来取代系统的栈将递归算法变成非递归算法。
![clip_image002 clip_image002](http://www.cppblog.com/images/cppblog_com/woaidongmao/WindowsLiveWriter/cb09d6aaaf8a_13D48/clip_image002_thumb.jpg)
图5-2 普通树的先序遍历流程图
![clip_image003 clip_image003](http://www.cppblog.com/images/cppblog_com/woaidongmao/WindowsLiveWriter/cb09d6aaaf8a_13D48/clip_image003_thumb.jpg)
图5-3 普通树的后序遍历流程图
![clip_image004 clip_image004](http://www.cppblog.com/images/cppblog_com/woaidongmao/WindowsLiveWriter/cb09d6aaaf8a_13D48/clip_image004_thumb.jpg)
图5-4 树的宽度方向遍历流程图
3. 不使用栈的非递归遍历算法
对于普通树来说,也可以设计出不使用栈的非递归遍历算法,不过这要求每个节点都保存它的父节点指针,不使用栈的非递归遍历算法流程如图5-5所示。
![clip_image005 clip_image005](http://www.cppblog.com/images/cppblog_com/woaidongmao/WindowsLiveWriter/cb09d6aaaf8a_13D48/clip_image005_thumb.jpg)
图5-5 不使用栈的普通树的非递归遍历流程图