首先树是一种递归结构，因此递归算法很好写，关键是非递归算法。

而非递归算法中，树的四种非递归遍历方式又是核心。下面先介绍树的四种非递归遍历算法，再介绍其他的非递归算法。

1、层次遍历：

这大概是最简单的了，队列结构，先进根节点，然后循环：出队列头，然后分别进左，右子树节点。如此反复，直至队列为空。

2、先序遍历：

单栈即可。这个在三序遍历中最简单，因为栈只需要保存右子树节点，左子树直接访问。要点：访左存右。一层while循环即可搞定。

3、中序遍历：

单栈即可。这个要比先序难些，因为左右子树节点都要保存在栈中，因此分清父节点是否被访问过极为重要，不然就会无限循环。

怎么区分呢？可以这样区分：以tmp保存父节点，以tmp是否为空作为进栈条件（绝不可以tmp.left是否为空做为进栈条件，这样会分不清父节点是否访问过。不服可以写个试试），进栈后，tmp=tmp.left；出栈后，tmp=tmp.right。这样就可完美区分左右。

由于左节点要一次性进到底，所以总共需要两层while循环。要点：左路进到底，然后退一进右。如此反复。

4、后序遍历：

后序遍历就必须得用符号来标识左右了。实际上中序遍历不用符号已经令我很吃惊，不过中序右子树只保存一层，因此还可以区分左右。但后序左右子树均要保存多层，不用符号就无法区分左右。

实际上后序遍历和中序遍历很像，更实际上，三种遍历的顺序是一样的，先序因为先访问节点，所以不保存左子树，故和后两序差别较大。

因此我们可以仿照中序遍历的写法来写后序。只不过加上符号，标明左右。

会写中序非递归遍历，就会写后序非递归遍历。要点：左路进到底，判断符号，左则变号进右，右则退栈输出。如此反复。

另外切记：直接以tmp ！= null 而不是tmp.left != null 作为左子树递进条件。写循环的要点在于一次把一层写完，而不是一次写残缺多层。

另外：进栈时，我们是知道左右的，出栈时就不知道了。出栈想要防止重复访问，就需要特殊的访问技巧（中序）和特殊的标记符号（后序）。

其余还有一些琐碎算法，基本都是树的几种遍历算法的应用：

1、通过前序与中序确定二叉树。前序首节点是根节点，中序，根节点左右为左右子树。据此不断划分，递归构建即可。

2、n个节点二叉树的个数与n个元素的出栈顺序一样，均为卡特兰树。(1/(n+1)) * C(2n,n).

java代码如下：