二叉树的先中后序遍历

给定数据结构

    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("pre-order: ");
        if (head != null) {
            Stack<Node> stack = new Stack<Node>();
            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();
    }

中序：

思路：

如果当前结点的左孩子不为空就一直压入左孩子，直到该节点的左孩子为空，就弹出当前结点并打印，然后压入右孩子，如果右孩子为空就该弹出并打印当前结点的父节点，依次执行下去，注意代码中的while控制条件

代码：

public static void inOrderUnRecur(Node head) {
        System.out.print("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.print(head.value + " ");
                    head = head.right;
                }
            }
        }
        System.out.println();
    }

---

后序：

思路：

后序的顺序是左右中，在先序的非递归中，我们的实现了中左右的顺序，后序我们改成中右左的顺序，然后把实现中右左顺序的栈压入一个新的栈，就变成左右中了。在这里说的先序的中左右是指打印顺序而不是具体的入栈顺序，因为先序有一步是先弹出中，打印，再入而不是中左右同时入

代码：

    public static void posOrderUnRecur1(Node head) {
        System.out.print("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.push(head.left);
                }
                if (head.right != null) {
                    s1.push(head.right);
                }
            }
            while (!s2.isEmpty()) {
                System.out.print(s2.pop().value + " ");
            }
        }
        System.out.println();
    }