详细遍历步骤如下:

  1. 根节点1进入队列。

image.png

  1. 节点1出队,输出节点1,并得到节点1的左孩子节点2、右孩子节点3。让节点2和节点3入队。

image.png

  1. 节点2出队,输出节点2,并得到节点2的左孩子节点4、右孩子节点5。让节点4和节点5入队。

image.png

  1. 节点3出队,输出节点3,并得到节点3的右孩子节点6。让节点6入队。

image.png

  1. 节点4出队,输出节点4,由于节点4没有孩子节点,所以没有新节点入队。

image.png

  1. 节点5出队,输出节点5,由于节点5同样没有孩子节点,所以没有新节点入队。

image.png

  1. 节点6出队,输出节点6,节点6没有孩子节点,没有新节点入队。

image.png

到此为止,所有的节点都遍历输出完毕。

import java.util.LinkedList;
import java.util.Queue;

public class BFS {

    public static void main(String[] args) {
        Node[] tree = createTree();
        BFSShow(tree[0]);
    }

    //创建二叉树
    public static Node[] createTree() {
        Node[] treeNodes = new Node[10];
        for (int i = 0; i < treeNodes.length; i++) {
            treeNodes[i] = new Node(i);
        }
        for (int i = 0; i < 10; i++) {
            if (i * 2 + 1 < 10) {
                treeNodes[i].left = treeNodes[i * 2 + 1];
            }
            if (i * 2 + 2 < 10) {
                treeNodes[i].right = treeNodes[i * 2 + 2];
            }
        }
        return treeNodes;
    }


    //广度遍历
    public static void BFSShow(Node tree) {
        //创建队列
        Queue<Node> nodes = new LinkedList<>();
        //把根节点加入队内
        nodes.offer(tree);
        
        while (!nodes.isEmpty()) {
            Node node = nodes.poll();

            if (node.left != null)
                nodes.offer(node.left);
            if (node.right != null)
                nodes.offer(node.right);
            System.out.println(node.data);
        }
    }
}

//定义树节点
class Node {
    int data;
    Node left;
    Node right;

    Node() {
    }

    Node(int data) {
        this.data = data;
    }
}
最后修改:2021 年 09 月 17 日 05 : 29 PM