二叉树的先序、中序和后序遍历，递归与非递归方式实现。

二叉树遍历

如图是一个二叉树：

二叉树的先序遍历顺序为根、左、右；中序遍历为左、根、右；后序遍历为左、右、根。

首先是一个节点类Node

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

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

然后通过递归方式实现三种二叉树遍历的方式，很简单：

    // 先序遍历递归实现
    public void preOrderRecur(Node head) {
        if (head == null) {
            return;
        }
        System.out.println(head.value + " ");
        preOrderRecur(head.left);
        preOrderRecur(head.right);
    }

    // 中序遍历递归实现
    public void inOrderRecur(Node head) {
        if (head == null) {
            return;
        }
        inOrderRecur(head.left);
        System.out.println(head.value + " ");
        inOrderRecur(head.right);
    }

    // 后序遍历递归实现
    public void posOrderRecur(Node head) {
        if (head == null) {
            return;
        }
        posOrderRecur(head.left);
        posOrderRecur(head.right);
        System.out.println(head.value + " ");
    }

然后是稍微复杂一点的非递归方式实现。

先序遍历
1.申请一个新的栈，记为stack，然后将头结点head压如stack中。
2.从stack中弹出栈顶节点，记为cur，然后打印cur节点的值，再将节点cur的右孩子（不为空的话）先压入stack中，最后将cur的左孩子（不为空的话）压入stack中。
3.不断重复步骤2，直到stack为空，全部过程结束。

    // 先序遍历非递归实现
    public void preOrderUnRecur(Node head) {
        System.out.println("pre-order: ");
        if (head != null) {
            Stack<Node> stack = new Stack<Node>();
            stack.add(head);
            while (!stack.isEmpty()) {
                head = stack.pop();
                System.out.println(head.value + " ");
                if (head.right != null) {
                    stack.add(head.right);
                }
                if (head.left != null) {
                    stack.add(head.left);
                }
            }
        }
        System.out.println();
    }

中序遍历
1.申请一个新的栈，记为stack。初始时，令变量cur = head。
2.先把cur节点压入栈中，对以cur节点为头的整棵子树来说，依次把左边界压入栈中，即不停地令cur = cur.left，然后重复步骤2。
3.不断重复步骤2，直到发现cur为空，此时从stack中弹出一个节点，记为node，打印node的值，并让cur = node.right，然后继续重复步骤2。
4.当stack为空且cur为空的时候整个过程停止。

    // 中序遍历非递归实现
    public void inOrderUnRecur(Node head) {
        System.out.println("in-order: ");
        if (head != null) {
            Stack<Node> stack = new Stack<Node>();
            while (!stack.isEmpty() || head != null) {
                if (head != null) {
                    stack.push(head);
                    head = head.left;
                } else {
                    head = stack.pop();
                    System.out.println(head.value + " ");
                    head = head.right;
                }
            }
        }
        System.out.println();
    }

后序遍历
1.申请一个栈，记为s1，在申请一个栈，记为s2。然后将头结点head压入s1中。
2.从s1中弹出的节点记为cur，然后依次将cur的左孩子和右孩子压入s1中。
3.在整个过程中，每一个从s1中弹出的节点都放进s2中。
4.不断重复步骤2和步骤3，直到s1为空，过程停止。
5.从s2中依次弹出节点并打印，打印的顺序就是后序遍历的顺序。

    // 后序遍历非递归实现
    public void posOrderUnRecur(Node head) {
        System.out.println("pos-order: ");
        if (head != null) {
            Stack<Node> s1 = new Stack<Node>();
            Stack<Node> s2 = new Stack<Node>();
            s1.push(head);
            while (!s1.isEmpty()) {
                head = s1.pop();
                s2.push(head);
                if (head.left != null) {
                    s1.add(head.left);
                }
                if (head.right != null) {
                    s1.add(head);
                }
            }
            while (!s2.isEmpty()) {
                System.out.println(s2.pop().value + "");
            }
        }
    }