1.二叉树的前中后序遍历的递归及非递归实现

首先写定义Node类（Node.java）

public class Node {

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

二叉树遍历的递归写法
1.前序遍历

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

2.中序遍历

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

3.后序遍历

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

以上过程比较简单，不再赘述
重点是二叉树遍历的非递归写法（参考左程云的那本书）：
1.前序遍历

    public void preOrderUn(Node head)
    {
        System.out.println("pre-order:");
        if(head != null)
        {
            Stack<Node> stack = new Stack<>();
            stack.push(head);
            while(!stack.isEmpty())
            {
                Node cur = stack.pop();
                System.out.print(cur.value+" ");
                if(cur.right != null)
                    stack.push(cur.right);
                if(cur.right != null)
                    stack.push(cur.right);
            }
        }
    }

借用栈结构，先将头结点压入栈中，然后在栈非空的时候，弹出栈顶元素并打印，如果该元素有孩子，就先将右孩子压入，再将左孩子压入，如此循环往复即可
2.中序遍历

public void inOrderUn(Node head)
    {
        if(head != null)
        {
            Stack<Node> stack = new Stack<>();
            while(head != null || !stack.isEmpty())
            {
                if(head != null)
                {
                    stack.push(head);
                    head = head.left;
                }else {
                    head = stack.pop();
                    System.out.print(head.value + " ");
                    head = head.right;
                }
            }
        }
    }

还是利用了栈结构，因为递归就是系统在帮我们压栈和弹栈。先一直将该节点的左孩子压入栈中，直到该节点为空，然后弹出栈顶元素并打印，将该节点的右孩子（如果不为空的话）压入，如此循环
3.后序遍历

public void posOrderUn(Node head)
    {
        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 + " ");
            }
        }
    }

利用了两个栈，s1的逻辑和前序遍历栈的逻辑差不多，只是先压入左孩子，再压入右孩子，s1每弹出一个元素，s2就将该元素压入栈中，最后一次弹出s2中的元素即可。