BFS

🔵 ThingsILearned

✔️ BFS는 QUQUE로 작동함.

Queue는 Last in First out.

✅ BFS 탐색하기

class Node{
    int data;
    Node lt, rt;

    public Node(int value){
        data= value;
        lt= rt= null;
    }
}
class Main {
    Node root;
    public void BFS(Node root){
        Queue<Node> Q= new LinkedList<>();
        Q.offer(root);
        int level=0;

        while(!Q.isEmpty()){
            int len= Q.size();
            System.out.print(level+ ": ");
            for(int i=0; i<len; i++){
                Node cur= Q.poll();
                System.out.print(cur.data+ " ");
                if(cur.lt != null) Q.offer(cur.lt);
                if(cur.rt != null) Q.offer(cur.rt);
            }
            level++;
            System.out.println();
        }
    }
    public static void main(String[] args) {
        Main tree = new Main();
        tree.root= new Node(1);
        tree.root.lt= new Node(2);
        tree.root.rt= new Node(3);
        tree.root.lt.lt= new Node(4);
        tree.root.lt.rt= new Node(5);
        tree.root.rt.lt= new Node(6);
        tree.root.rt.rt= new Node(7);
        tree.BFS(tree.root);
    }
}



//⭐️output:
0: 1
1: 2 3
2: 4 5 6 7

(14) BFS는 Queue로 작동하므로 linked list생성
🟠 이때 linked list의 제너릭 타입 Node로 주는 것 기억하기
(15) 먼저 root를 Queue에 offer하고
(16) 지금 어떤 level에 있는지 알려주기 위해 level 만듦. 첫 레벨은 0.
(18) Queue에 모든 요소가 poll되어 비우게 되면 멈추기
(19) Q.size()만큼 for돌면서 그 레벨에 있는 요소들 출력해야 함
🟠 Q.size() 만큼 돌아야 하니까 Q.size()를 나타내는 변수 필요, len
(21) 현재 가장 앞에 있는 node를 poll해서 프린트
(23) 그리고 방금 poll한 노드의 왼쪽, 오른쪽 자식을 탐색해서 Queue에 offer
(24, 25) 주의할 점은 노드의 왼쪽, 오른쪽 자식이 null이면 안된다는 것임!
자식이 null이면 가장 말단 노드라는 것이니까 추가할 것이 없음.
(27) 이제 이 level은 다 탐색했으니 다음 level로 넘어가기 위해 level++
(28) 보기 편하라고 한 줄 띄움