文档介绍：遍历二叉树的非递归算法
摘要:文章对二叉树遍历算法进行简要分析,通过简单示例介绍三种遍历的内在关系,使用C语言引出它的非递归算法。
关键词:二叉树子树结点非递归算法

二叉树的建立是数据结构和算法设计中不可缺少的内容。在电子计算机刚刚发明时,人们主要使用其迭代、判断功能进行方程式中根的求精计算,所用到的数据仅为整型或实型即能满足要求,计算求精课程称作数值方法,而当时的数据结构被称作表处理。随着电子计算机向非数值计算的管理领域发展,所涉及到的问题越来越复杂;若解决同一个问题,构造不同的数据结构会对应复杂程度不同的算法,而设计一个合适的数据结构能使算法的复杂程度大大降低。编程人员在实践中体会到;学好一种高级语言仅能解决三成所遇到的问题,而学好数据结构却能解决八成所遇到的问题,因此,在软件设计中选择一个合适的数据结构越发显得重要。
在管理科学领域中,很多问题都可以转化为树
Tree型结构,而多叉树又都可以转化为一棵等价的二叉树Bi―Tree。在这里二叉树的定义为:或者为空、或者由根与两棵互不相交,称为根结点左子树和右子树的二权树组成,即二叉树本身还是由二叉树组成;由此可见二权树的定义是递归的Recursive。二叉树具有结构简单、操作方便的优点,能够在遍历Traverse过程中建立二权树的链式存储结构;使一个非线性结构的管理问题线性化。从而使很多管理领域中的问题,都可以在二叉树的建立与遍历过程中得到解决,。
遍历二叉树是指以某种次序访问二叉树中的每个结点,并且每个结点仅被访问一次。这个“访问”含义应该说是比较广的,可以是查询结点数据域的内容、输出结点的数据、修改结点的数据或者是执行对结点的其他操作。假设遍历时访问结点仅是输出结点数据域的值,那么遍历的结果将是得到一个线性序列。由于二叉树有左、右子树,所以遍历的次序不同,得到的结果就会不同。
在介绍遍历算法之前,先介绍一下遍历的具体方法。例如有一棵二叉树,它有4个结点。为了便于理解遍历思想,暂时为每个没有子树的结点都补充上相应的空子树
,用△表示,。
设想有一条搜索路线(),它从根结点的左支开始,自上而下从左至右搜索,最后由根结点右支向上出去。不难看出,若考虑空子树的话,恰好搜索路线途经每个有效结点都是三次。把第一次经过就访问的结点列出,它们是A、B、D、C,这就是先根遍历的结果。那么第二次经过才访问的则是中根遍历,其结果是B、D、A、C。第三次经过才访问的是后根遍历,结果是D、B、C、A。
在二叉树的应用中,常常需要对树中的所有结点逐一进行处理,或者在树中查找某些特定的结点。这就提出了一个遍历二叉树的问题,即: 怎样按照某条路径访问树中的每一个结点,使每一个结点都被访问一次,且仅被访问一次。这里的“访问”的含义很广, 比如修改或输出结点的信息,删除结点等等。
我们知道,二叉树有三个基本的组成部分,即:根,左子树和右子树,只要依次遍历这三个部分,就能遍历整个二叉树。遍历二叉树的方式通常有三种,即:先序遍历(先访问根结点,再访问左子树,最后访问右子树)、中序遍历(先访问左子树,再访问根结点,最后访问右子树)。后序遍历(先访问左子树,再访问右子树,最后访问根结点)。由于二叉树