二叉树递归和非递归遍历

二叉树递归和非递归遍历2015-09-04二叉树是一种非常重要的数据结构，很多其他数据机构都是基于二叉树的基础演变过来的。二叉树有前、中、后三种遍历方式，因为树的本身就是用递归定义的，因此采用递归的方法实现三种遍历，不仅代码简洁且容易理解，但其开销也比较大，而若采用非递归方法实现三种遍历，则要用栈来模拟实现（递归也是用栈实现的）。下面先简要介绍三种遍历方式的递归实现，再详细介绍三种遍历方式的非递归实现。

一、三种遍历方式的递归实现（比较简单，这里不详细讲解）

1、先序遍历——按照“根节点-左孩子-右孩子”的顺序进行访问。

void pre_traverse（BTree pTree）{if（pTree）{printf（"%c ",pTree->data）;if（pTree->pLchild）pre_traverse（pTree->pLchild）;if（pTree->pRchild）pre_traverse（pTree->pRchild）;}}

2、中序遍历——按照“左孩子-根节点-右孩子”的顺序进行访问。

void in_traverse（BTree pTree）{if（pTree）{if（pTree->pLchild）in_traverse（pTree->pLchild）;printf（"%c ",pTree->data）;if（pTree->pRchild）in_traverse（pTree->pRchild）; }}

3、后序遍历——按照“左孩子-右孩子-根节点”的顺序进行访问。

void beh_traverse（BTree pTree）{if（pTree）{if（pTree->pLchild）beh_traverse（pTree->pLchild）;if（pTree->pRchild）beh_traverse（pTree->pRchild）;printf（"%c ",pTree->data）;}

二、三种遍历方式的非递归实现

为了便于理解，这里以下图的二叉树为例，分析二叉树的三种遍历方式的实现过程。