二叉树的前序、中序、后序遍历实现(递归+非递归)

        把LeetCode上二叉树的三序遍历做了，有个问题。本来想直接将LinkedList清空再重新放的，结果怎么搞都不行。还是对C语言指针概念匮乏啊，汇编也没学过的我哭qq。不过我通过重新new对象还是达到了想要的结果。

        List<Integer> list = new LinkedList<>();
        ......
        list = null;
        list = new LinkedList<>();

        这样就搞定了。将list指向新的堆空间。

一、二叉树的前序遍历

        二叉树的前序遍历其实就是先访问根结点，再前序遍历根结点的左子树，最后前序遍历根结点的右子树。

1、递归版

        递归版很容易想，直接根据定义一步到位。

	private void preOrderTraversal(Node<E> node) {
        if (node == null)
            return;
        System.out.print(node.element + " ");    
        preOrderTraversal(node.left);
        preOrderTraversal(node.right);
    }

2、非递归版

        观察前序遍历的访问顺序，一路往左访问，访问右结点的时候和之前往左遍历的顺序是相反的，可以借助栈将右子树入栈，不能往左访问的时候就出栈，不断循环，栈为空则遍历结束。

	private void preOrder(Node<E> node) {
        Stack<Node<E>> stack = new Stack<>();

        while (true) {
            if (node != null) {
                System.out.print(node.element + " ");
                if (node.right != null)
                    stack.push(node.right);
                node = node.left;
            } else {
                if (!stack.isEmpty())
                    node = stack.pop();
                else
                    break;
            }
        }
    }

二、二叉树的中序遍历

        二叉树的中序遍历其实就是先中序遍历根结点的左子树，再访问根结点，最后中序遍历根结点的右子树。

1、递归版

        根据定义一步到位。

	private void inOrderTraversal(Node<E> node) {
        if (node == null)
            return;
        inOrderTraversal(node.left);
        System.out.print(node.element + " ");     
        inOrderTraversal(node.right);
    }

2、非递归版

        观察中序遍历的访问顺序，一路往左遍历，先要访问的是不能再往左走的结点，访问左结点的顺序和往左遍历的顺序也是相反的，借助栈将一路往左时候经历的结点都入栈。不能往左的时候，将栈顶元素弹出并访问，并看看弹出的结点是否有右结点，不断循环，栈为空则遍历结束。

	private void inOrder(Node<E> node) {
        Stack<Node<E>> stack = new Stack<>();
        while (true) {
            if (node != null) {
                stack.push(node);
                node = node.left;
            } else {
                if (!stack.isEmpty()) {
                    node = stack.pop();
                    System.out.print(node.element + " ");
                } else
                    break;
                node = node.right;
            }
        }
    }

三、二叉树的后序遍历

       二叉树的后序遍历其实就是先后序遍历根结点的左子树，再后序遍历根结点的右子树，最后访问根结点。

1、递归版

       根据定义一步到位。

	private void postOrderTraversal(Node<E> node) {
        if (node == null)
            return;
        postOrderTraversal(node.left);
        postOrderTraversal(node.right);
        System.out.print(node.element + " ");   
    }

2、非递归版

       观察后序遍历的访问顺序，其实是先某个结点的左结点，再访问它的右结点，最后访问自己。借助栈按照和访问时候反着的顺序将结点依次入栈。当遇到叶子结点或者上次弹出结点的父结点是这次栈顶的结点的时候，就从栈顶弹出元素并访问。栈为空，遍历结束。

	private void postOrder(Node<E> node) {
        Stack<Node<E>> stack = new Stack<>();
        stack.push(node);
        Node<E> prevNode = null;
        while (!stack.isEmpty()) {
            Node<E> top = stack.peek();
            if ((top.left == null && top.right == null) || (prevNode != null && prevNode.parent == top)) {
                prevNode = stack.pop();
                System.out.print(prevNode.element + " ");
            } else {
                if (top.right != null)
                    stack.push(top.right);
                if (top.left != null)
                    stack.push(top.left);
            }
        }
    }