Java二叉树的广度优先搜索（BFS）实现详解-java教程-PHP中文网

Java二叉树的广度优先搜索（BFS）实现详解

霞舞

发布： 2025-11-16 14:16:02

原创

861人浏览过

java二叉树的广度优先搜索（bfs）实现详解

本文旨在详细介绍如何在Java中实现二叉树的广度优先搜索（BFS）算法。通过避免直接获取兄弟节点，并利用队列的特性，我们能够保证按照层次顺序遍历二叉树的所有节点。文章将提供完整的代码示例和详细的步骤说明，帮助读者理解并掌握BFS算法在二叉树中的应用。

广度优先搜索（BFS）是一种用于遍历或搜索树或图数据结构的算法。它从树的根节点开始，沿着树的宽度遍历节点。也就是说，它先访问所有相邻的节点，然后再访问下一层相邻的节点。在二叉树的场景下，BFS通常用于按层级顺序访问节点。

二叉树节点定义

首先，定义一个简单的二叉树节点类 Node，包含数据、左右子节点以及访问标记：

public class Node {
    int data;
    Node left;
    Node right;
    boolean visited;

    Node(int data) {
        this.data = data;
        this.left = null;
        this.right = null;
        this.visited = false;
    }

    // Getter and setter methods (omitted for brevity)
    public int getData() {
        return data;
    }

    public Node getLeft() {
        return left;
    }

    public Node getRight() {
        return right;
    }

    public void setVisited(boolean visited) {
        this.visited = visited;
    }

    public boolean isVisited() {
        return visited;
    }
}

登录后复制

BFS算法实现

核心思想是使用队列来维护待访问的节点。首先将根节点入队，然后循环执行以下步骤：

立即学习“Java免费学习笔记（深入）”；

从队列中取出一个节点。
访问该节点（例如，将其数据添加到结果列表中）。
将该节点的左右子节点（如果存在）依次入队。

关键点在于，不要试图直接获取节点的兄弟节点。只需要将当前节点的子节点按顺序入队，就能保证按照层级顺序访问节点。

纳米搜索

纳米搜索：360推出的新一代AI搜索引擎

查看详情

以下是BFS算法的Java实现：

import java.util.LinkedList;
import java.util.Queue;
import java.util.ArrayList;
import java.util.List;

public class BFS {

    public static List<Node> bfs(Node root) {
        Queue<Node> queue = new LinkedList<>();
        List<Node> result = new ArrayList<>();

        if (root == null) {
            return result;
        }

        queue.add(root);

        while (!queue.isEmpty()) {
            Node node = queue.poll();
            result.add(node); // 访问节点

            // 将子节点加入队列
            if (node.left != null) {
                queue.add(node.left);
            }
            if (node.right != null) {
                queue.add(node.right);
            }
        }

        return result;
    }

    public static void main(String[] args) {
        // 创建二叉树
        Node node1 = new Node(1);
        Node node7 = new Node(7);
        Node node9 = new Node(9);
        Node node8 = new Node(8);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        node1.left = node7;
        node1.right = node9;
        node7.right = node8;
        node9.right = node3;
        node9.left = node2;

        // 执行BFS
        List<Node> bfsResult = bfs(node1);

        // 打印结果
        for (Node node : bfsResult) {
            System.out.println(node.getData());
        }
    }
}

登录后复制

代码解释：

bfs(Node root) 方法接收二叉树的根节点作为输入，并返回一个包含按BFS顺序访问的节点的列表。
Queue<Node> queue 使用 LinkedList 实现队列，用于存储待访问的节点。
List<Node> result 用于存储访问结果。
在 while 循环中，从队列中取出一个节点，将其添加到结果列表中，然后将该节点的左右子节点（如果存在）添加到队列中。

使用示例

在 main 方法中，创建了一个简单的二叉树，并调用 bfs 方法进行遍历。遍历结果将按层级顺序打印到控制台。

注意事项

空树处理： 代码首先检查根节点是否为空，如果为空，则直接返回一个空列表，避免空指针异常。
节点访问时机： 在节点从队列中取出时访问该节点，而不是在添加到队列时访问。这保证了正确的层级顺序。
避免重复访问： 在更复杂的图结构中，可能需要使用 visited 标记来避免重复访问节点。但在二叉树中，由于每个节点最多有两个子节点，且不会形成环路，因此可以省略 visited 标记以简化代码。