[JAVA] BFS - 이진트리레벨탐색

문제

- 이진트리 레벨 탐색하기

- 큐 사용

 

0레벨부터 N레벨까지 레벨 별로 탐색하기

- 일단 root노드를 0레벨에 만들고, 큐에 루트 노드를 넣는다.

- while문에서 큐에 원소가 없어질때까지 큐에 있는 원소 개수(레벨에 있는 원소 개수)만큼 출력해준다.

 

- queue에서 queue의 크기만큼 노드를 꺼내서 출력한다.

- 왼쪽과 오른쪽 자식이 있는 경우 현재 노드에서 왼쪽 자식과 오른쪽 자식 노드를 큐에 넣어준다.

if(current.lt!=null) if(current.rt!=null)

 

for이 종료되면 해당 레벨 탐색이 끝났다는 뜻으로, 레벨을 증가시킨다.

큐에 원소가 모두 제거되면 탐색을 종료한다.

class Node{
    int data;
    Node lt, rt;
    public Node(int val){
        data=val;
        lt=rt=null;
    }
}
public class Solution {
    Node root;
    public void BFS(Node root){
        Queue<Node> Q = new LinkedList<>();
        Q.offer(root);
        int L = 0; // root 노드 레벨은 0
        while(!Q.isEmpty()){
            int len = Q.size(); // Q의 원소의 개수
            System.out.print(L+" : "); // 해당 레벨의 원소들은 무엇이 있는지 출력
            for(int i=0; i<len; i++){ // 해당 레벨의 원소들이 모두 여기에서 나와야 함
                Node current = Q.poll(); // 노드 꺼내기
                System.out.print(current.data+" ");

                // 왼쪽, 오른쪽 자식을 queue에 넣어줘야 함
                if(current.lt!=null){
                    Q.offer(current.lt);
                }
                if(current.rt!=null){
                    Q.offer(current.rt);
                }
            }
            // for문이 끝나면 레벨 끝
            L++;
            System.out.println();
        }

    }
    public static void main(String[] args) {
        Solution tree = new Solution();
        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);
    }
}