用非递归方式实现二叉树的先序、中序、后序遍历

提示:由于本人没有精力做那么多流程图，建议你看的时候自己在纸上画一画，模拟一下顺序，不然很难理解。

1.先序遍历

思路：
（1）用一个栈保存二叉树的节点，从根节点开始。
（2）先压入根节点，打印，然后找右孩子，存在就压入栈，不存在就压入左孩子。
（3）栈非空，且既没有右孩子也没有左孩子的时候，弹出栈顶元素并打印，继续第2步。

由于操作的顺序是：先让父结点出栈并打印，然后压右，再压左。出栈顺序就正好相反，先弹左，后弹右，实现了先序遍历。

public static void preOrderUnRecur(Node head) {
        System.out.print("先序遍历: ");
        if (head != null) {
            Stack<Node> stack = new Stack<>();
            stack.add(head);
            while (!stack.isEmpty()) {
                head = stack.pop();
                System.out.print(head.value + " ");
                if (head.right != null)
                    stack.push(head.right);
                if (head.left != null)
                    stack.push(head.left);
            }
        }
        System.out.println();
    }

2.中序遍历：

思路：
（1）当前节点先把自己的左边界（所有的左孩子节点）都压到栈里。
（2）由于一直重复head = head.left，肯定会有一个时刻，head.left为空，当节点为空的时候，开始弹栈。
具体操作是：从栈中拿出栈顶元素并打印，然后当前节点向右孩子移动。
（3）重复前两步，当栈为空且节点也为空时，循环结束。

public static void inOrderUnRecur(Node head) {
        System.out.print("中序遍历: ");
        if (head != null) {
            Stack<Node> stack = new Stack<>();
            while (!stack.isEmpty() || head != null) {
                if (head != null) {
                    stack.push(head);
                    head = head.left;
                } else {
                    head = stack.pop();
                    System.out.print(head.value + " ");
                    head = head.right;
                }
            }
        }
        System.out.println();
    }

3.后序遍历：

• 方法1 （使用两个栈）

后序遍历的顺序是 左→右→中，要想压到栈里再按这个顺序弹出打印的话，压栈的时候顺序就应该是 中→右→左。那么，怎么实现呢？

我们前面写第一个先序遍历的时候，顺序是中左右。稍微修改一下先序遍历的代码，让那个栈弹出并打印中节点之后，先压入右孩子，再压入左孩子。这样出栈顺序就变成了中右左。

继续修改，弹栈时候栈顶元素不打印，而是压入另一个辅助栈，原来那个栈的出栈打印顺序（中右左）就变成了辅助栈的压栈顺序。那么在辅助栈弹栈打印的时候，不就是左右中了吗？

这个解释起来比较晦涩，自己拿张纸画一下流程，模拟出栈顺序，你就会很明白。

public static void posOrderUnRecur1(Node head) {
        System.out.print("后序遍历: ");
        if (head != null) {
            Stack<Node> s1 = new Stack<>();
            Stack<Node> s2 = new Stack<>();
            s1.push(head);
            while (!s1.isEmpty()) {
                head = s1.pop();
                s2.push(head);
                if (head.left != null)
                    s1.push(head.left);
                if (head.right != null)
                    s1.push(head.right);
            }
            while (!s2.isEmpty()) {
                System.out.print(s2.pop().value + " ");
            }
        }
        System.out.println();
    }

• 方法2
  纯粹炫技的做法，只用了一个栈，能看得懂就看，看不懂也没有关系。

public static void posOrderUnRecur2(Node h) {
        System.out.print("后序遍历: ");
        if (h != null) {
            Stack<Node> stack = new Stack<>();
            stack.push(h);
            Node c;
            while (!stack.isEmpty()) {
                c = stack.peek();
                if (c.left != null && h != c.left && h != c.right) {
                    stack.push(c.left);
                } else if (c.right != null && h != c.right) {
                    stack.push(c.right);
                } else {
                    System.out.print(stack.pop().value + " ");
                    h = c;
                }
            }
        }
        System.out.println();
    }

完整的代码（包含了递归方式）：

import java.util.Stack;

public class PreInPosTraversal {

    public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int data) {
            this.value = data;
        }
    }

    public static void preOrderRecur(Node head) {
        if (head == null) return;
        System.out.print(head.value + " ");
        preOrderRecur(head.left);
        preOrderRecur(head.right);
    }

    public static void inOrderRecur(Node head) {
        if (head == null) return;
        inOrderRecur(head.left);
        System.out.print(head.value + " ");
        inOrderRecur(head.right);
    }

    public static void posOrderRecur(Node head) {
        if (head == null) return;
        posOrderRecur(head.left);
        posOrderRecur(head.right);
        System.out.print(head.value + " ");
    }

    public static void preOrderUnRecur(Node head) {
        System.out.print("先序遍历: ");
        if (head != null) {
            Stack<Node> stack = new Stack<>();
            stack.add(head);
            while (!stack.isEmpty()) {
                head = stack.pop();
                System.out.print(head.value + " ");
                if (head.right != null)
                    stack.push(head.right);
                if (head.left != null)
                    stack.push(head.left);
            }
        }
        System.out.println();
    }

    public static void inOrderUnRecur(Node head) {
        System.out.print("中序遍历: ");
        if (head != null) {
            Stack<Node> stack = new Stack<>();
            while (!stack.isEmpty() || head != null) {
                if (head != null) {
                    stack.push(head);
                    head = head.left;
                } else {
                    head = stack.pop();
                    System.out.print(head.value + " ");
                    head = head.right;
                }
            }
        }
        System.out.println();
    }

    public static void posOrderUnRecur1(Node head) {
        System.out.print("后序遍历: ");
        if (head != null) {
            Stack<Node> s1 = new Stack<>();
            Stack<Node> s2 = new Stack<>();
            s1.push(head);
            while (!s1.isEmpty()) {
                head = s1.pop();
                s2.push(head);
                if (head.left != null)
                    s1.push(head.left);
                if (head.right != null)
                    s1.push(head.right);
            }
            while (!s2.isEmpty()) {
                System.out.print(s2.pop().value + " ");
            }
        }
        System.out.println();
    }

    public static void posOrderUnRecur2(Node h) {
        System.out.print("后序遍历: ");
        if (h != null) {
            Stack<Node> stack = new Stack<>();
            stack.push(h);
            Node c;
            while (!stack.isEmpty()) {
                c = stack.peek();
                if (c.left != null && h != c.left && h != c.right) {
                    stack.push(c.left);
                } else if (c.right != null && h != c.right) {
                    stack.push(c.right);
                } else {
                    System.out.print(stack.pop().value + " ");
                    h = c;
                }
            }
        }
        System.out.println();
    }

    public static void main(String[] args) {
        Node head = new Node(5);
        head.left = new Node(3);
        head.right = new Node(8);
        head.left.left = new Node(2);
        head.left.right = new Node(4);
        head.left.left.left = new Node(1);
        head.right.left = new Node(7);
        head.right.left.left = new Node(6);
        head.right.right = new Node(10);
        head.right.right.left = new Node(9);
        head.right.right.right = new Node(11);

        // recursive
        System.out.println("==============递归==============");
        System.out.print("先序遍历: ");
        preOrderRecur(head);
        System.out.println();
        System.out.print("中序遍历: ");
        inOrderRecur(head);
        System.out.println();
        System.out.print("后序遍历: ");
        posOrderRecur(head);
        System.out.println();

        // unRecursive
        System.out.println("============非递归=============");
        preOrderUnRecur(head);
        inOrderUnRecur(head);
        posOrderUnRecur1(head);
        posOrderUnRecur2(head);

    }

}