二叉树前序，中序，后序遍历的迭代实现，实现思路及代码

用Java描述数据结构之二叉树，前序遍历，中序遍历，后序遍历这篇博客中我介绍了二叉树的相关概念和递归实现的二叉树的前中后序遍历。今天来介绍非递归迭代版遍历的思路及实现代码。
首先我们要明白所谓遍历就是集合中每个节点都要经过，就下面这棵树而言，我们从根节点开始要怎么走才能经过每个节点？

下面是上图树的构建代码：

public static TreeNode buildTree() {// 博客中所用到的树的构建TreeNode a = new TreeNode('a');TreeNode b = new TreeNode('b');TreeNode c = new TreeNode('c');TreeNode d = new TreeNode('d');TreeNode e = new TreeNode('e');TreeNode f = new TreeNode('f');TreeNode g = new TreeNode('g');TreeNode h = new TreeNode('h');a.left = b; a.right = c;b.left = d; b.right = e;c.left = f; c.right = g;e.right = h;return a;}

很明显我们要从根节点出发，左右都可以走，一般我们习惯往左走，我们一路向左走，直到走到没路可走，即cur == null，用代码实现这个是这样的：

//root为根节点
Treenode cur = root;while(cur != null){cur = cur.left;
}

二叉树遍历前序中序后序、直到我们走到空之后，下一步该怎么办？

每个节点都有左右两个方向可走，我们选择一路向左，走到头之后我们应该退一步，然后向右走，然后再向左走，再走到尽头，往回走，向右走一步。。。。。。。就这样去探路。拿例子来演示如下：

从A出发向左走，到尽头之后退一步到B往B的右边走一步到E，继续向左走，走到头之后退一步到E，再向右走到H，继续向左走，走到尽头之后退一步。。。。。。
我们把上述过程中的退一步称为回溯，想要实现回溯我们就必须从刚开始向左走的过程中记录经过的每个节点，而这个回溯很明显具有后入先出的特性，这让我们想到用栈去记录（递归版遍历实际也是通过栈回溯，不过是java虚拟机栈，每一个栈帧都是以此方法的调用）每走到尽头之后回溯一个节点，然后往这个节点的右边走，就这样直到栈空了，也就遍历完了。代码实现如下：

		TreeNode cur = root;Stack<TreeNode> stack = new Stack<>();//第一次进入时stack为空，但是cur != null //所以 cur != null 是为第一次能进入循环专门设置的条件//当stack为空时结束循环 while (cur != null || !stack.isEmpty()){while (cur != null){//入栈每个经过的节点，向左走到尽头时回溯stack.push(cur);//向左走cur = cur.left;}//回溯TreeNode pop = stack.pop();//向右走cur = pop.right;}

现在我们来说明前序遍历和中序遍历（后序遍历有点不同后面细说）：
每个节点都会经过第一次经过然后向左走，回溯回来经过第二遍然后向右走，向右走完还会回来经过第三遍像下图：

我们吧第一次经过处理节点称为先序遍历或者前序遍历，第二次经过时处理称为中序遍历，第三次经过时处理称为后序遍历。
因为前序遍历是在第一次经过时处理，体现在代码中就是：
先序遍历代码：

//先序遍历
public static void preorder(TreeNode root){TreeNode cur = root;Stack<TreeNode> stack = new Stack<>();while (cur != null || !stack.isEmpty()){while (cur != null){stack.push(cur);System.out.print((char)cur.val + " ");cur = cur.left;}cur = stack.pop().right;}}

那么中序遍历就是第二次经过也就是左走到尽头回溯的时候处理节点

//中序遍历public static void inorder(TreeNode root){TreeNode cur = root;Stack<TreeNode> stack = new Stack<>();while (cur != null || !stack.isEmpty()) {while (cur != null) {stack.push(cur);cur = cur.left;}TreeNode pop = stack.pop();System.out.print((char)pop.val + " ");cur = pop.right;}}

二叉树的遍历算法图解？理解了先序和中序遍历之后再来看后序遍历！！！

剩下就是后续遍历了，为什么说后序遍历相对前两种要麻烦一点呢。
我们来一步一步执行一下前序遍历：

1. cur指向root，入栈
   

2. 向左走，走到B，入栈
   

3. 层序遍历二叉树？向左走到D，入栈
   

4. 再向左走，走到 cur == null 了，回溯一个节点，并向右走，执行下面代码：

			TreeNode pop = stack.pop();cur = pop.right;

此时栈中是这样的

走到这里还没有发现问题，后续遍历第一个节点也恰巧是D。继续走

5. 因为D的右边还是 null，所以需要继续回溯，继续执行那段代码：

			TreeNode pop = stack.pop();cur = pop.right;

这次从栈中出来的的B节点，但是后序遍历第二个节点不应该是B，此时的cur指向了E，并且因为E != null,E入栈，此时栈中是这样：

6. 向E的左边走，发现E的左边是空，那么就要执行回溯操作

			TreeNode pop = stack.pop();cur = pop.right;

二叉树后序遍历怎么看？E会出栈，栈中如下：

7. 因为E的右边是H不为null，所以H入栈，此时栈中如下：

走到这里我们就可以停下来了，这棵树的后序遍历是：D H E B F G C A，但是上述的过程中，还没到第三次经过节点很多节点像B E 节点都已经出栈了，H节点走完之后就直接回溯到A节点了，如果要后续遍历，H节点完了应该先回到E， 回到B 再回到A才对。现在这个代码在第二次经过的时候就已经让节点出栈，所以这个代码对于后序遍历不适用。

所谓后序遍历就是在第三次经过节点的时候才对节点进行相应的处理，也就是遍历完右子树回来的时候才做处理，所以现在的关键是怎么才能知道当前是从节点左边回来还是从右边回来的问题。

我们需要定义一个引用last指向上一个出栈的节点，然后在每次回溯的时候判断last是不是该节点的右孩子，如果是右孩子则说明是从右边回溯的，如果不是就是左边回溯，左边回溯不用出栈，右边回溯才出栈，在出栈时执行打印，通过代码理解：

public static void postorder(TreeNode root){Stack<TreeNode> stack = new Stack<>();TreeNode cur = root;//专门用来记录上一个出栈的节点TreeNode last = null;while (cur != null || !stack.isEmpty()){while (cur != null){stack.push(cur);cur = cur.left;}//这里用peek看last是否是右孩子//peek.right == null 是用来判断当前节点有没有右孩子//没有右孩子就没必要执行else里的代码让cur往右走了//就像D节点，在这里判断了没有右孩子就直接出栈了，没必要在往其右走再回来TreeNode peek = stack.peek();if (peek.right == null || peek.right == last){System.out.print((char)peek.val + " ");last = peek;stack.pop();}else {cur = peek.right;}}}

下面通过执行代码验证三个遍历：

public class Main {public static TreeNode buildTree() {TreeNode a = new TreeNode('a');TreeNode b = new TreeNode('b');TreeNode c = new TreeNode('c');TreeNode d = new TreeNode('d');TreeNode e = new TreeNode('e');TreeNode f = new TreeNode('f');TreeNode g = new TreeNode('g');TreeNode h = new TreeNode('h');a.left = b; a.right = c;b.left = d; b.right = e;c.left = f; c.right = g;e.right = h;return a;}public static void main(String[] args) {TreeNode root = buildTree();System.out.print("前序遍历：");Preorder.preorder(root);System.out.println();System.out.print("中序遍历：");Inorder.inorder(root);System.out.println();System.out.print("后序遍历：");Postorder.postorder(root);}
}