二叉树的广度优先遍历(BFS)与深度优先遍历

文章目录

• 概述
• 广度优先遍历（BFS）
• • 算法思想
  • 代码实现
• 深度优先遍历（DFS）
• • 算法思想
  • 代码实现
  • • 1. 递归实现
    • 2. 非递归（栈）实现
• 参考资料

概述

深度优先遍历（Depth First Search, 简称 DFS） 与广度优先遍历（Breath First Search）是遍历树和图的两种非常重要的算法，本文通过相关资料学习，记录BFS与DFS的算法思想与代码实现。本文章主要是对二叉树的遍历进行叙述，后续更新图的BFS和DFS遍历。

广度优先遍历（BFS）

广度优先遍历，指的是从图的一个未遍历的节点出发，先遍历这个节点的相邻节点，再依次遍历每个相邻节点的相邻节点。即一层一层的遍历。

算法思想

算法思想是使用队列。
1.先将根节点入队列，再将根节点出队列，将根节点的左右节点依次入队（如果存在的话）；
2.出队列的头部元素，将所出元素的左右节点入队列（如果存在的话）。
3.依次按照第二步遍历，直到队列为空结束。
算法思想如下图所示：

代码实现

定义二叉树：

private static class Node {
        
        public int value;	//节点值
        public Node left;	//左节点
        public Node right;	//右节点

        public Node(int value, Node left, Node right) {	//构造器
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }

BFS代码实现：

/**
 * 队列实现BFS
 */
public static void bfs(Node root) {
    if (root == null) {
        return;
    }
    Queue<Node> queue= new LinkedList<>();
    queue.add(root);

    while (!queue.isEmpty()) {
        Node node = queue.poll();
        //输出当前遍历到的节点
        System.out.println("value = " + node.value);
        Node left = node.left;
        if (left != null) {
            queue.add(left);
        }
        Node right = node.right;
        if (right != null) {
            queue.add(right);
        }
    }

深度优先遍历（DFS） 算法思想

深度优先遍历主要思路是从图中一个未访问的顶点 V 开始，沿着一条路一直走到底，然后从这条路尽头的节点回退到上一个节点，再从另一条路开始走到底…，不断递归重复此过程，直到所有的顶点都遍历完成，它的特点是不撞南墙不回头，先走完一条路，再换一条路继续走。

代码实现

DFS的实现依靠递归和栈。

1. 递归实现

递归实现比较简单，由于是前序遍历，所以我们依次遍历当前节点，左节点，右节点即可，对于左右节点来说，依次遍历它们的左右节点即可，依此不断递归下去，直到叶节点（递归终止条件）。

/**
*	递归实现DFS
*/
public static void dfs(Node treeNode) {
        if (treeNode == null) {
            return;
        }
        // 输出当前遍历到的节点
        System.out.println("value = " + node.value);
        // 遍历左节点
        dfs(treeNode.left);
        // 遍历右节点
        dfs(treeNode.right);
    }

递归的表达性很好，也很容易理解，不过如果层级过深，很容易导致栈溢出。

2. 非递归（栈）实现

思路：
1、对于每个节点来说，先遍历当前节点，然后把右节点压栈，再压左节点（这样d栈的时候会先拿到左节点遍历，符合深度优先遍历要求）
2、d栈，拿到栈顶的节点，如果节点不为空，重复步骤 1， 如果为空，结束遍历。
整体动态图如下图所示：

/**
 * 使用栈来实现 dfs
 */
public static void dfsWithStack(Node root) {
    if (root == null) {
        return;
    }
    Stack<Node> stack = new Stack<>();
    // 先把根节点压栈
    stack.push(root);
    while (!stack.isEmpty()) {
        Node treeNode = stack.pop();
         // 输出当前遍历到的节点
        System.out.println("value = " + node.value);
        // 先压右节点
        if (treeNode.right != null) {
            stack.push(treeNode.right);
        }
        // 再压左节点
        if (treeNode.left != null) {
            stack.push(treeNode.left);
        }
    }
}

以上就是关于二叉树的 BFS 和 DFS 思想介绍和代码实现。

参考资料

1. https://blog.csdn.net/gene1994/article/details/85097507
2. https://developer.aliyun.com/article/756316