二叉树前序、中序、后序遍历非递归写法

package dayone.tre;

import java.util.Stack;

public class PreorderTraversal {

    /***
     * 先序遍历非递归写法
     * @param head
     */
    public static void preorderTraversal(Node head) {
        System.out.println("Preorder Traversal");

        if (head == null) {
            return;
        }

        Stack<Node> stack = new Stack<>();
        stack.add(head);
        while (!stack.isEmpty()) {
            //将节点弹出，然后先放入弹出的右子节点,再放入左子节点,由于栈先进后出，所以下次进来时pop的为左子节点，循环往复
            head = stack.pop();
            System.out.println(head.value);

            if (head.right != null) {
                stack.push(head.right);
            }
            if (head.left != null) {
                stack.push(head.left);
            }
        }
    }

    /***
     * 中序遍历非递归写法
     * @param head
     */
    public static void inOderUnRecur(Node head) {
        System.out.println("in-order");
        if (head == null) {
            return;
        }
        Stack<Node> stack = new Stack<>();
        while (!stack.isEmpty() || head != null) {
            if (head != null) {
                //不断将左节点入栈直至左节点全部入栈
                stack.push(head.left);
                head = head.left;
            } else {
                //弹出节点，兵器将节点的右子节点入栈,右子节点如果有左子节点则继续满足head！=null,则继续入栈
                head = stack.pop();
                System.out.println(head.value);
                head = head.right;
            }
        }
    }

    /***
     * 后序遍历
     * @param head
     */
    public static void posOrderUnRecur(Node head) {
        System.out.println("pos-order");
        if (head == null) {
            return;
        }
        Stack<Node> s1 = new Stack<>();
        Stack<Node> s2 = new Stack<>();
        s1.add(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()) {
            //从s2中依次出栈
            System.out.println(s2.pop().value);
        }
    }
}
class Node {
    public int value;

    public Node left;

    public Node right;

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