首先树是一种递归结构，因此递归算法很好写，关键是非递归算法。
而非递归算法中，树的四种非递归遍历方式又是核心。下面先介绍树的四种非递归遍历算法，再介绍其他的非递归算法。
1、层次遍历：
这大概是最简单的了，队列结构，先进根节点，然后循环：出队列头，然后分别进左，右子树节点。如此反复，直至队列为空。
2、先序遍历：
单栈即可。这个在三序遍历中最简单，因为栈只需要保存右子树节点，左子树直接访问。要点：访左存右。一层while循环即可搞定。
3、中序遍历：
单栈即可。这个要比先序难些，因为左右子树节点都要保存在栈中，因此分清父节点是否被访问过极为重要，不然就会无限循环。
怎么区分呢？可以这样区分：以tmp保存父节点，以tmp是否为空作为进栈条件（绝不可以tmp.left是否为空做为进栈条件，这样会分不清父节点是否访问过。不服可以写个试试），进栈后，tmp=tmp.left；出栈后，tmp=tmp.right。这样就可完美区分左右。
由于左节点要一次性进到底，所以总共需要两层while循环。要点：左路进到底，然后退一进右。如此反复。
4、后序遍历：
原文：http://www.cnblogs.com/zqiguoshang/p/6498831.html