行文结构
递归方法（前中后）
非递归方法（前中后层）
微软面试题
二叉树遍历根据“根节点”遍历时相对的次序分为前序、中序、后序。图示为相对于根节点的次序，左右子树也是一样的规则。
前序遍历 中序遍历 后续遍历
1. 递归方法
前序遍历
<a></a>
中序遍历
后续遍历
整合参考程序
View Code
结果
2. 非递归方法
非递归方法借助于栈，“记忆”走过的结点。
“根-左孩子-右孩子”，对每一个结点看成是根节点，先输出，后入栈（到时返回访问右孩子），然后访问左孩子。当不能在往左走时，查询栈中的记忆，根据栈顶进入右孩子，重复上边的故事。
“左孩子-根-右孩子”，对每一个结点看成是根节点，先入栈（到时返回访问自己和右孩子），然后访问左孩子。当不能在往左走时，查询栈中的记忆，根据栈顶访问自己并且进入右孩子，重复上边的故事。
“左孩子-右孩子-根”，为了达到这个效果，需要把把按“根-->右孩子-->左孩子”的顺序入栈，因为栈的特征是先进后出，所以访问时顺序相反。对于一个结点只有满足以下两个条件时，才访问，否则按“根-->右孩子-->左孩子”顺序入栈。
左右孩子全为NULL
前边访问的结点正好为当前结点的左孩子或右孩子(访问了左孩子必定已经访问了右孩子)
结果同递归遍历
层次遍历
3. 微软面试题
分析：由二叉遍历树变成有序的结构，不用说绝对是中序遍历。中序遍历分为两种方法——递归、非递归。递归不需要额外的空间，非递归需要额外空间（借助与栈）。现在用两种方法实现，其思路都是基本中序遍历的改进。
方法一（递归方法）
执行程序
方法二（非递归方法）
本文转自jihite博客园博客，原文链接：http://www.cnblogs.com/kaituorensheng/p/3431409.html，如需转载请自行联系原作者