Java二叉树广度优先搜索（BFS）实现指南：避免“兄弟节点”陷阱

public class Node {
    int data;
    Node left;
    Node right;
    // 在二叉树遍历中，如果无环，visited 字段通常不是必须的，
    // 但在通用图的BFS中用于避免重复访问和死循环。
    // boolean visited; 

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

    // 实际应用中可根据需要添加 getter/setter 方法
    public int getData() {
        return data;
    }
}

// 构建示例二叉树
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;

// 树结构示意:
//        1
//       / \
//      7   9
//       \ / \
//        8 2 3

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

public class BinaryTreeBFS {

    // Node 类定义 (同上，为完整性再次提供)
    public static class Node {
        int data;
        Node left;
        Node right;

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

        public int getData() {
            return data;
        }
    }

    /**
     * 实现二叉树的广度优先搜索（BFS）遍历。
     *
     * @param root 二叉树的根节点。
     * @return 包含按BFS顺序访问的所有节点的列表。
     */
    public static List<Node> bfs(Node root) {
        Queue<Node> queue = new LinkedList<>(); // 使用 LinkedList 作为 Queue 的实现
        List<Node> result = new ArrayList<>(); // 用于存储遍历结果

        if (root == null) {
            return result; // 如果根节点为空，直接返回空列表
        }

        queue.add(root); // 将根节点加入队列，等待处理

        while (!queue.isEmpty()) {
            Node currentNode = queue.poll(); // 从队列头部取出节点，此节点被“访问”
            result.add(currentNode); // 将当前节点加入结果列表

            // 将当前节点的左子节点（如果存在）加入队列
            if (currentNode.left != null) {
                queue.add(currentNode.left);
            }
            // 将当前节点的右子节点（如果存在）加入队列
            if (currentNode.right != null) {
                queue.add(currentNode.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;

        System.out.println("BFS 遍历结果：");
        List<Node> bfsResult = bfs(node1);
        for (Node node : bfsResult) {
            System.out.print(node.getData() + " ");
        }
        // 预期输出: 1 7 9 8 2 3
    }
}