이진트리탐색(BFS)

너비우선탐색은 자신에게 가까운 노드들을 먼저 탐색한다.
자신의 가까운 노드들을 다 탐색한 뒤 가까운 노드들의 가까운 노드를 탐색한다.

        1
   2        3
4   5    6   7
와 같은 구조의 이진트리가 있을 때

1에 가까운 2,3을 탐색
-> 2,3에 가까운 4,5,6,7 탐색 하여

1 2 3 4 5 6 7 순으로 탐색한다.
이를 코드로 구현하면

public class Main {

    static Node root;

    public static void main(String[] args) {
        nodeSetting();
        bfs();
    }

    public static void bfs(){
        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            int len = queue.size();
            for(int i = 0; i<len; i++){
                Node current = queue.poll();
                System.out.print(current.data + " ");
                if(current.ln != null)queue.offer(current.ln);
                if(current.rn != null)queue.offer(current.rn);
            }
        }

    }

    public static class Node{
        int data;
        Node ln = null;
        Node rn = null;

        public Node(int data){
            this.data = data;
        }
    }

    public static void nodeSetting(){
        root = new Node(1);
        root.ln = new Node(2);
        root.rn = new Node(3);
        root.ln.ln = new Node(4);
        root.ln.rn = new Node(5);
        root.rn.ln = new Node(6);
        root.rn.rn = new Node(7);
    }
}

queue에 한 레벨의 노드들을 넣는다.

가장 상위레벨의 node는 1이므로 1부터 시작한다.

같은 레벨의 노드들을 꺼내 출력한 뒤, 그 노드들의 자식노드를 다시 queue에 넣는다.

queue를 순회하며 노드를 제거할 때 해당 노드의 자식 노드를 바로 저장하며 queue의 데이터가 실시간으로 달라지기 때문에 foreach가 아닌 for문을 사용해야 한다.