vlambda博客
学习文章列表

二叉树的前、中、后、层序遍历

二叉树的遍历

遍历:把二叉树中所有节点都访问一遍且只访问一次。

二叉树有以下四种遍历方式:

  • 前序遍历: 先访问父节点,再遍历左子树和右子树。

  • 中序遍历: 先遍历左子树,再访问父节点,再遍历右子树。

  • 后序遍历: 先遍历左子树,再遍历右子树,最后访问父节点。

  • 层序遍历:也叫层次遍历,从根节点开始往下一层一层的遍历节点。

小结: 看访问父节点的顺序,就能确定是前序,中序还是后序遍历。

前序遍历

前序遍历的访问顺序为:父节点、前序遍历左子树、前序遍历右子树。

下面的二叉树前序遍历的结果为7、4、2、1、3、5、9、8、11、10、12

前序遍历的代码实现:

    /**
     * 前序遍历
     */

    public void preorder({
        preorder(root);
    }

    private void preorder(Node<E> node{

        if(null == node) {
            return;
        }

        System.out.println(node.value);

        if(null != node.left) {
            preorder(node.left);
        }

        if(null != node.right) {
            preorder(node.right);
        }

    }

前面的前序遍历只实现了对节点的打印,如果想要自定义对节点的操作以及访问到某个节点就终止遍历,怎么实现?

下面实现对前序遍历的增强:

增加遍历接口:

    public static abstract class Vistor<E{

        protected boolean stop;

        /**
         * 遍历节点
         * @param e
         * @return true-停止遍历,false-继续遍历
         */

        public abstract boolean visit(E e);

    }

前序遍历增强方法:

    /**
     * 前序遍历增强
     */

    public void preorder(Vistor<E> vistor{
        if (null == root || null == vistor) {
            return;
        }
        preorder(root, vistor);
    }

    private void preorder(Node<E> node, Vistor<E> vistor{

        // 每次遍历前先判断标志位stop是否为true
        if (null == node || vistor.stop) {
            return;
        }

        // 将stop置为true,停止遍历
        vistor.stop = vistor.visit(node.value);

        if (null != node.left) {
            preorder(node.left, vistor);
        }

        if (null != node.right) {
            preorder(node.right, vistor);
        }

    }

中序遍历、后序遍历、层次遍历的增强与前序遍历增强类似。

中序遍历

中序遍历的访问顺序:中序遍历左子树、父节点、中序遍历右子树。

下面的二叉树中序遍历的结果为1、2、3、4、5、7、8、9、10、11、12

二叉树的前、中、后、层序遍历

中序遍历的访问顺序也可以是:中序遍历右子树、根节点、中序遍历左子树。这样访问上面的结果为12、11、10、9、8 、7、5、4、3、2、1,可见二叉搜索树的中序遍历结果是升序或者降序的。

中序遍历的代码实现:

    /**
     * 中序遍历
     */

    public void inorder({
        inorder(root);
    }

    private void inorder(Node<E> node{

        if(null == node) {
            return;
        }

        if(null != node.left) {
            inorder(node.left);
        }

        System.out.println(node.value);

        if(null != node.right) {
            inorder(node.right);
        }

    }

后序遍历

后序遍历的访问顺序:后序遍历左子树、后序遍历右子树、父节点。

下面的二叉树后序遍历的结果为1、3、2、5、4、8、10、12、11、9、7

后序遍历的代码实现:

    /**
     * 后序遍历
     */

    public void postorder({
        postorder(root);
    }

    private void postorder(Node<E> node{

        if(null == node) {
            return;
        }

        if(null != node.left) {
            postorder(node.left);
        }

        if(null != node.right) {
            postorder(node.right);
        }

        System.out.println(node.value);

    }

层序遍历

层序遍历的访问顺序:从上到下、从左到右依次访问每一个节点

下面的二叉树层序遍历的结果为7、4、9、2、5、8、11、1、3、10、12


层序遍历的思路:使用队列

  1. 将根节点入队

  2. 循环执行以下操作,直到队列为空

    1. 将队头节点A出队,进行访问

    2. 将A的左子节点入队

    3. 将A的右子节点入队

层序遍历的代码实现:

    /**
     * 层序遍历
     */

    public void levelOrder() {
        if (null == root) {
            return;
        }

        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {

            Node<E> node = queue.poll();

            System.out.println(node.value);

            if(null != node.left) {
                queue.offer(node.left);
            }

            if(null != node.right) {
                queue.offer(node.right);
            }

        }

    }