6.2 二叉树遍历

  在实际的编程中，二叉树是一种非常常见的数据结构。常见的二叉树有AVL树、红黑树和哈夫曼树。其中AVL树和红黑树是排序二叉树。排序二叉树的特征就是对于每个节点，左子节点比自己小，右子节点比自己大。对于一般的树，有用栈实现的深度优先遍历和用FIFO队列实现的广度优先遍历。但是对于二叉树有特定的三种遍历方法，分别是前序遍历、中序遍历和后序遍历。
  以下是一个排序二叉树的例子。

  先看看前序遍历,前序遍历Preorder Traversal，与深度优先搜索DFS效果一致，这里就不多说了。
  中序遍历Inorder Traversal对排序二叉树特别重要，为什么呢？中序遍历是先访问左子树，再访问自己，再访问右子树。其效果呢，恰好形成了从小到大的遍历。请看下图：

  所以中序遍历的意义在于排序。但是后序遍历Postorder Traversal，后序遍历是先访问左子节点，再访问右子节点，最后访问自己。这么做最大的用途是用来做删除操作，删除肯定是最后处理自己的。

  递归实现的代码比较容易，以下是三种遍历的递归实现

    public void preOrder(Predicate> visitor) {
        final Deque> nodes = new ArrayDeque<>();
        if (!visitor.test(this)) {
            return;
        }

        if (this.getLeft() != null) {
            getLeft().preOrder(visitor);
        }

        if (this.getRight() != null) {
            getRight().preOrder(visitor);
        }
    }

    
    public void inOrder(Predicate> visitor) {
        final Deque> nodes = new ArrayDeque<>();

        if (this.getLeft() != null) {
            getLeft().inOrder(visitor);
        }

        if (!visitor.test(this)) {
            return;
        }

        if (this.getRight() != null) {
            getRight().inOrder(visitor);
        }
    }

    
    public void postOrder(Predicate> visitor) {
        final Deque> nodes = new ArrayDeque<>();

        if (this.getLeft() != null) {
            getLeft().postOrder(visitor);
        }

        if (this.getRight() != null) {
            getRight().postOrder(visitor);
        }
        if (!visitor.test(this)) {
            return;
        }
    }

  对于二叉树的前序遍历，直接使用栈进行DFS就行了。可以参考本专栏前一篇文章，这里不再赘述。但是中序遍历和后序遍历如何不通过递归实现呢？
  中序遍历也是用栈，不过是方法不一样。初始化栈时，先把整个左子树放入栈中。然后出栈的时候，把右节点的整个左子树放进去。代码稍微复杂了一点，如下：

    public void inOrderWithStack(Predicate> visitor) {
        final Deque> stack = new ArrayDeque<>();

        BinaryNode left = (BinaryNode) getRoot();
        while (left != null) {
            stack.push(left);
            left = left.left;
        }
        while (!stack.isEmpty()) {
            BinaryNode node = stack.pop();
            if (!visitor.test(node)) {
                break;
            }
            if (node.right != null) {
                BinaryNode l = node.right;
                while (l != null) {
                    stack.push(l);
                    l = l.left;
                }
            }
        }
    }

  后序遍历，因为是用来删除的，根结点最后访问，对于这种最后访问的场景，我们自然想到了栈。所以我们自然想到的是使用双栈算法，第一个栈用于DFS，然后将遍历出来的元素压入第二个栈。再从第二个栈访问。代码我是复用了DFS的代码，如下：

    public void postOrderTwoStacks(Predicate> visitor) {
        Deque> stack = new linkedList<>();
        dfs(x->{
            stack.push(x);
            return true;
        }, false);
        while (!stack.isEmpty()){
            Node node = stack.poll();
            if (!visitor.test(node)) {
                break;
            }
        }
    }