二叉树的前中后序递归和非递归遍历操作【代码】

“遍历”是二叉树各种操作的基础，可以在遍历过程中对节点进行各种操作，如：求节点的双亲，求节点的孩子，判断节点的层次，当然，还有一些更重要的操作，例如，依据遍历序列建立二叉树，，再如，对建立的二叉树进行线索化，等等。

二叉树的各种遍历操作必须了然于心，无论是递归的，还是非递归的。递归算法的优点是形式简单，当然，正如一句话所说“迭代是人，递归是神。”递归算法的整个详细过程还是很烧脑的，每一步都把未知当作已知，每一步又在把未知变为已知。想不到描述起来又用上了递归的概念，生活中其实有很多递归的现象，我印象最深的就是两面面对面放置的镜子，你永远也找不到最深处的自己（当然我们假设你的视力无限好同时光在反射过程中没有亮度损失），也就是说这个递归过程没有边界条件，会无限递归，永远也不会返回，这在程序中可就是死循环呀，相当可怕，CPU很快就会被掏空。所以每次设计递归算法时，首先要考虑到的就是边界返回条件。还有一个我印象很深的电影，《盗梦空间》，三层梦境，从现实中进入第一层，再从第一层梦境进入第二层，最后再从第二层进入第三层。当然电影里也说了可以无限往下递归，进入一个叫迷失域的地方，不过好在电影的设定是无论你掉入了多深的梦，你只要在梦里死了，就能返回上层梦境，也就是说，每层梦境都有一个返回条件，所以原则上是不会死循环的。。。

哎呀，扯太远了，其实我一直想写一篇关于递归的哲学文章，阐述程序和我们现实的联系，算了，不扯了。

递归形式上很简单，代码很简洁，然后时间复杂度却很大，同时还得花费一定的空间复杂度（栈递归深度），比如经典的Hanoi问题，时间复杂度是O(2^n),n为圆盘的个数，时间复杂度膨胀的很厉害。所以我们在很多时候不能依赖于递归算法，而需要去寻找相应的非递归算法。比如计算一个数的阶乘，递归算法

原文：https://www.cnblogs.com/journal-of-xjx/p/9315155.html