前言：
上一篇文章，我们讨论了二叉树的递归遍历。而对于二叉树来说，最简单的也莫过于它的递归遍历了。在学习非递归遍历的时候，不得不说。。一点头绪都没有（一开始，二叉树的非递归遍历真的感觉好难懂，思路一直没法理顺，想先放过，看后面章节的内容，结果发现二叉查找树、优先队列中的二叉堆问题等等，都和树有着很多的联系。虽然解决他们的方法和非递归遍历没有太大的关系，但却能够说明自己对树的理解是否深刻。因为没办法深刻理解树，就没法进行树其他方面的内容，比如结点的insert、delete、伸展树、B树等等，尤其是二叉堆的堆序性质，虽然找到最小元很简单，即根，但是要把它其余元素再重新找到该放置的点，就需要更深的理解。。这方方面面实在太多，必须得先啃掉第一块硬骨头。。）说了太多废话。。还是进入今天的正题~~二叉树的非递归遍历。
今天将放上两种不同思路的代码，并在我学习过程中觉得不好理解的地方进行标注。
<pre name="code" class="java"><span style="white-space:pre"></span>/** * 遇到一个结点，就把它压栈，并去遍历它的左子树。 * 当左子树遍历完后，从栈顶弹出这个结点并去访问他 * 然后按其右指针再去中序遍历该结点的右子树 * @param p */// 非递归实现中序遍历1public static void inorder1(node p){Stack<node> stack = new Stack<node>();node n = p;while(n != null || stack.size() > 0){while(n != null){//一直向左，并将沿途结点压人栈中stack.push(n);n = n.getLeft();}if(stack != null){n = stack.pop();visitKey(n);n = n.getRight();}}}public static void inorder2(node p) {Stack<node> stack = new Stack<node>();while (p != null) {while (p != null) {if (p.getRight() != null)stack.push(p.getRight());// 当前节点右子入栈stack.push(p);// 当前节点入栈p = p.getLeft();}p = stack.pop();while (!stack.empty() && p.getRight() == null) {visitKey(p);p = stack.pop();}visitKey(p);if (!stack.empty())p = stack.pop();elsep = null;}}/** 非递归实现前序遍历1*/protected static void prefixOrder2(node p) {Stack<node> stack = new Stack<node>();node node = p;while (node != null || stack.size() > 0) {while (node != null) {// 压入所有的左节点，压入前访问它。//左节点压入完后pop访问右节点。visitKey(node);stack.push(node);node = node.getLeft();}if (stack.size() > 0) {//node = stack.pop();node = node.getRight();}}}<span style="white-space:pre"></span>/** 非递归实现前序遍历(根左右) */protected static void iterativePreorder(node p) {Stack<node> stack = new Stack<node>();if (p != null) {stack.push(p);while (!stack.empty()) {p = stack.pop();visitKey(p);// 为什么p.getLeft()在后，getRight()在前// 因为while循环第一句就是pop// visit所以要把left放上，先访问。之中方法是即压即访问法。if (p.getRight() != null)stack.push(p.getRight());if (p.getLeft() != null)stack.push(p.getLeft());}}}
（如果想测试，就把代码复制到上一篇文章里面就可以）
以上是非递归实现前序遍历和中序遍历。根据代码可以看出中序遍历2和先序遍历2的思路大致相同，不同点在于访问结点的位置。一开始不理解的时候总觉得出栈和访问时一样的，但实际上是访问的时候才是输出，输出的方法为visitKey()。其实当理解了这两种方法以后感觉并不难，重点就是真正的把那张图看懂，二叉树的访问顺序究竟是怎样的。（后序遍历的代码之后放上~）非递归遍历过程的核心在于遍历过程中经过的结点的路线是一样的，只是访问各个结点的时机不同！
好了，非递归实现前序遍历和中序遍历说完，再谈最后一种遍历方式：层序遍历。层序遍历是使二维结构的二叉树按照一维结构输出，即二维结构的线性化。难点：当访问完某结点n的左孩子后，如何再访问n的右孩子，以及如何记录n的右孩子和n结点本身。
解决办法：
需要一个存储结构保存暂时不被访问的结点。这时候我们选择的是堆栈或者队列。前面我们讲的都是用堆栈实现，现在我们说一下如何用队列实现：遍历从根结点开始，，首先将根结点入队，然后开始执行循环：结点出队、访问该结点、其左右儿子入队。代码如下：
（输出结果是按从上往下，从右到左的顺序输出，即为层序遍历）
<span style="white-space:pre"></span>/** * 层序遍历 * @param p */public static void levelOrder(node root){if(root == null) return;//首先判断树是否为空Queue<node> q = new LinkedList<node>();//建立队列q.add(root);while(!q.isEmpty()){node n = q.poll();visitKey(n);//访问得到的结点，即输出结点if(n.getLeft() != null){//判断该结点是否存在左孩子，然后入队q.add(n.getLeft());}if(n.getRight() != null){q.add(n.getRight());}}}
造物之前，必先造人。
