数据结构|二叉树的深度优先遍历和广度优先遍历

数据结构|二叉树的深度优先遍历和广度优先遍历

Scroll Down

0. 前言

最近开始刷树的题了,打算好好总结一下树的相关题目,树最重要的思想是递归,因为树的结构本来就是一个递归的结构。而对于树的问题,最重要的方法就是遍历。我把树的遍历总结为两部分:

  • 基于策略的遍历
    深度优先遍历(DFS)
    广度优先遍历(BFS)
  • 基于访问顺序的遍历
    前序遍历
    中序遍历
    后续遍历

其实前中后序遍历从遍历策略上来讲都属于深度优先遍历,但是为了好记忆,将他们单独分类了。今天就先来总结一下基于策略的遍历。基于策略的遍历,顾名思义,就是根据不同的策略去遍历一棵树。我们所采取的策略是深度优先和广度优先。

1. 深度优先遍历

深度优先遍历(Depth First Search,DFS),是一种用于遍历或搜索树或图的算法。沿着树的深度遍历树的节点,尽可能深的搜索树的分支。当节点v的所在边都己被探寻过,搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点,则选择其中一个作为源节点并重复以上过程,整个进程反复进行直到所有节点都被访问为止。属于盲目搜索。

深度优先遍历根据访问节点的顺序不同,可以分为前序遍历、中序遍历、后续遍历,关于三种基于访问顺序的遍历,过两天再总结,此处不再展开。本文所采取的是前序遍历。

我们给定一颗二叉树,利用深度优先遍历,对于每个节点,我们都采取根-左-右的方式访问,则访问节点的顺序依次是:A、B、D、E、C、F、G。

二叉树.png

二叉树的定义,采用Leetcode的二叉树的定义,如下:

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

深度优先遍历的实现方式有两种,一种是采用递归的方法,而另一种是采用非递归的方法。

1.1 递归方法

递归的方法比较好理解,从根节点出发,每次先递归访问自己的左子节点,再递归访问自己的右子节点。

    public static void preOrder(TreeNode root) {
        if(root == null)return;
        System.out.print(root.val+" ");
        preOrder(root.left);//先递归访问自己的左子节点
        preOrder(root.right);//再递归访问自己的右子节点
    }

优点:从问题本身的逻辑角度来实现,代码简洁易懂。
缺点:速度慢,递归的本质就是函数嵌套函数,造成了大量的重复计算。

1.2 非递归方法

非递归的方法必须要引入新的数据结构来对我们的遍历操作进行辅助。深度优先遍历采取的是利用栈的方法。

栈(stack)又名堆栈,它是一种运算受限的线性表。栈的特点是先进栈的元素后出栈(可以想象为一个竹筐,先放进去的东西只能后取出来)

对于上述二叉树,利用栈进行深度优先遍历的过程如下所示:

深度优先.png

当每个根节点进栈后,将其出栈,并判断其是否有子节点,如果有子节点,先将右节点入栈,再将左节点入栈(个人习惯,这样可以保证先出栈的是左节点)。重复该过程,直到栈为空。Java实现如下所示:

    public static void preOrder(TreeNode root){
        if(root==null) return;
        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode rnode = stack.pop();
            System.out.print(rnode.val);
	    //如果右子节点不为空,则入栈
            if(rnode.right!=null){
                stack.push(rnode.right);
            }
	    //如果左子节点不为空,则入栈
            if(rnode.left!=null){
                stack.push(rnode.left);
            }
        }
    }

优点:速度快,避免了重复计算。
缺点:代码不够简单,不好理解。

2. 广度优先遍历

广度优先遍历(Breadth First Search,BFS),又译作宽度优先遍历,或横向优先遍历,是一种图形搜索算法。简单的说,BFS是从根节点开始,沿着树的宽度遍历树的节点。如果所有节点均被访问,则算法中止。

对于上述二叉树,利用广度优先遍历,则访问节点的顺序依次是:A、B、C、D、E、F、G。

广度优先没有递归的方法,只能引入新的数据结构来对我们的遍历操作进行辅助。广度优先遍历采取的是利用队列的方法。

队列(queue),它是一种运算受限的线性表。队列的特点是先进队列的元素后先出队列(可以想象为一个管子,先进去的东西先从另一头出来)。

利用队列进行广度优先遍历的过程如下所示:

广度优先.png

当每个根节点进入队列后,将其出队列,并判断其是否有子节点,如果有子节点,先将左节点入队列,再将右节点入队列(个人习惯,这样可以保证先出队列的是左节点)。重复该过程,直到队列为空。Java实现如下所示:

    public static void levelOrder(TreeNode node){
        if(node==null) return;
        ArrayDeque<TreeNode> queue = new ArrayDeque<TreeNode>();
        queue.add(node);
        while(!queue.isEmpty()){
            TreeNode rnode = queue.remove();
            System.out.print(rnode.val+"  ");
            //如果左子节点不为空,则加入队列
            if(rnode.left!=null){
                queue.add(rnode.left);
            }
            if(rnode.right!=null){
                queue.add(rnode.right);
            }
        }

3. 总结

对于树,一定要掌握的操作就是遍历。不同的遍历方式,最后得到的结果不一样。感兴趣的朋友,可以看下Leetcode的第226题,翻转二叉树。可以通过深度优先遍历和广度优先来实现。

226题.png

答案:

/**
     * 递归(深度优先遍历)反转左右节点
     * @param root
     * @return
     */
    public TreeNode invertTree1(TreeNode root) {
        if (root==null) return null;
        //递归到当前节点的右根节点
        TreeNode right = invertTree1(root.right);
        //递归到当前节点的左根节点
        TreeNode left = invertTree1(root.left);
        //交换左右节点
        root.left = right;
        root.right = left;
        return root;
    }

    /**
     * 迭代(广度优先遍历)反转左右节点
     * @param root
     * @return
     */
    public TreeNode invertTree2(TreeNode root) {
        if (root==null) return null;
        //将整棵树放入队列中,迭代处理队列中的所有节点
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        //迭代
        while (!queue.isEmpty()){
            //每次从队列中拿一个节点。并交换这个节点的左右节点
            TreeNode temp = queue.poll();//出队列
            TreeNode left = temp.left;
            TreeNode right = temp.right;
            //交换节点
            temp.right = left;
            temp.left = right;
            //如果当前节点的左子树不为空,将左子树放入队列。
            if (temp.left!=null) queue.add(temp.left);
            //如果当前节点的右子树不为空,将左子树放入队列。
            if (temp.right!=null) queue.add(temp.right);
        }
        return root;
    }