二叉树（二）—遍历

按照一定的顺序( 原则)对二叉树中每一个结点都访问一次(仅访问一次), 得到一个由该二叉树的所有结点组成的序列，这一过程称为二叉树的遍历。

常用的遍历方法:1.前序遍历2.中序遍历3.后序遍历4.按层次遍历

对于如下二叉树
二叉树（二）—遍历

二叉树（二）—遍历
前序序列: A B D E J C F I G

递归算法的C语言实现如下：
二叉树（二）—遍历

二叉树（二）—遍历

中序序列:D B J E A F I C G

递归算法的C语言实现如下：
二叉树（二）—遍历

二叉树（二）—遍历
后序序列:D J E B I F G C A

递归算法的C语言实现，如下：
二叉树（二）—遍历

被遍历的二叉树非空,则按照层次从上到下,每一层从左到右依次访问结点。

上述二叉树按层次遍历序列为:A, B, C, D, E, F, G, J, I

按层遍历的C语言实现如下：
二叉树（二）—遍历

递归算法的优点
(1)问题的数学模型或算法设计方法本身就是递归的，采用递归算法来描述它们非常自然；
(2)算法的描述直观，结构清晰，且算法的正确性证明比非递归算法容易。

递归算法的不足
(1)算法的执行时间与空间开销往往比非递归算法要大，当问题规模较大时尤为明显；
(2)对算法进行优化比较困难；
(3) 分析跟踪算法的执行过程比较麻烦；
(4)描述算法的语言不具有递归功能时，算法无法描述。

以中序遍历为例，非递归算法设计如下：
二叉树（二）—遍历

其中，STACK[0: M-1]—保存遍历过程中结点的地址；
top—栈顶指针,初始为-1；
p—为遍历过程中使用的指针变量，初始时指向根结点。

C语言实现如下：
二叉树（二）—遍历