설명

이진트리를 레벨단위로 탐색하여 출력하세요.

코드

class Node{
    int data;
    Node lt,rt;

    public Node(int val) {
        data = val;
        lt=rt = null;
    }
}
public class BFS {
    Node root;

    public static void main(String[] args) {
        BFS tree = new BFS();
        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);
    }
    public void bfs(Node node){
        Queue<Node> que = new LinkedList<>();
        que.offer(node);
        int level = 0;
        while(!que.isEmpty()){
            System.out.println("level : "+level);
            int length = que.size();
            for(int i=0; i<length; i++){
                Node poll = que.poll();
                System.out.print(poll.data+" ");
                if(poll.lt != null) que.offer(poll.lt);
                if(poll.rt != null) que.offer(poll.rt);
            }
            System.out.println();
            level++;
        }
    }
}

지금까지 DFS(Depth First Search)를 연습했었다면 이번에는 BFS(Breadth Fisrt Search)를 연습하고자 한다. DFS는 실행시 가장 말단의 노드를 찍고 올라오면서 탐색하거나 가장 말단의 노드까지 탐색하며 내려가는 방법이였다면 BFS는 노드의 단계별 탐색을 하는 것을 의미한다.

우리가 코드에서 구현한 Node가 위 그림과 같은 트리 구조의 데이터를 가질 때

DFS의 경우

이러한 구조로 탐색하여 트리를 탐색한다고 생각하면 된다. 물론 전위 중위 후위에 따라 다를 수도 있지만 자세한건 검색해서 깊게 공부하길 추천한다.

BFS의 경우

위 두 그림처럼 단계별로

0단계
1
1단계
2 3
2단계
4 5 6 7

로 탐색하는 것을 의미한다. 그럼 코드를 살펴보자

우리는 자료구조 중 Queue를 사용하여 진행하게 되는데 que에는 우리가 출력해야할 데이터가 들어가 있다. 먼저 que에 첫번째로 tree.root를 넣고 시작하게 되는데 tree.root의 data값은 1이므로 1부터 차례대로 검사하기 시작한다. 모든 트리를 검사하기 위해 que가 비어있을때까지 반복하며 while 반복 내부에서는 tree의 자식 노드가 존재하는지 확인하기 위한 반복이 진행되어진다.

0단계
level = 0일때, que에는 root의 데이터 1개만 존재하므로 size는 1이되고 for문은 1번 반복된다. 반복문 내부에서는 que를 poll하여 root의 값을 반환받고 root.data의 1이 출력되어진다. 그리고 root.rt와 root.lt를 검사하여 null이 아니라면 que에 추가해준다. 마지막으로 level을 ++하여 증가시켜준다.

1단계
level = 1일때, que에는 최초 들어왔던 root의 lt와 rt 데이터가 들어가고 root는 poll되어 사라졌다. 이제 while의 조건에 que는 비어있지 않기때문에 실행되어지고 내부는 0단계와 똑같이 실행되어 2 3 이 출력되고 진행된다.

2단계
level = 2일때, que에는 데이터 4개가 들어와 있고 차례대로 4 5 6 7이 출력된다. 하지만 위의 반복과 다른점은 데이터의 lt와 rt가 null이므로 더이상 que에 값이 offer되지 않아 최종적으로 que는 비어있는 상태가 되므로 반복문이 종료되어진다.

위 단계를 모두 진행하면

결과 창에 다음과 같은 결과를 출력할 수 있게 된다.

DFS와 BFS의 개념을 정확히 구분하며 BFS의 단계적 검색 방법을 직접 코딩과 그림으로 그릴 줄 알아야한다!