[알고리즘] 7-7 이진트리 순회 - BFS(넓이우선탐색)(인프런 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 강의)

인프런의 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 강의를 수강하며 풀이 코드를 정리하고 있습니다.

• 문제 설명 : 이진트리를 넓이우선탐색(BFS)하는 문제

넓이우선탐색(BFS)란 시작 정점으로부터 가까운 정점을 우선적으로 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 탐색 방법으로 다음과 같은 순서로 탐색이 진행된다.

시작 정점으로부터 가까운 정점을 우선적으로 방문한다는 것은 시작 정점과 연결된 간선의 수가 적다는 것을 의미하기 때문에, 트리의 낮은 레벨부터 마지막 레벨까지 순차적으로 정점을 방문하며 탐색을 진행하게 된다.

코드

• 깊이 우선 탐색과 달리 재귀적으로 구현하지 않음
• Queue 자료구조를 이용해서 구현한다.
  • 어떤 정점을 방문했을 때, 자신을 출력하고, 자식이 있다면 큐에 넣는다.
  • 트리의 마지막 레벨까지 탐색을 완료하면 더 이상 큐에 넣을 자식들이 없기 때문에 큐의 사이즈는 0이 되고 탐색이 종료된다.
• 위 그림의 트리를 예시로 큐의 삽입 및 삭제 과정은 다음과 같다.
  1. 1 offer
  2. 1 poll -> 2,3 offer
  3. 2 poll -> 4, 5 offer
  4. 3 poll -> 6, 7 offer
  5. 4 poll -> 5 poll -> 6 poll -> 7 poll

package inflearn.recursive_tree_graph;

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

//이진트리 순회(넓이우선탐색 : 레벨탐색)
public class Main7_7 {

    public static void bfs(Node root) {
        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            int len = queue.size();

            for (int i = 0; i < len; i++) {
                Node node = queue.poll();
                System.out.print(node.data + " ");

                if (node.left != null) {
                    queue.offer(node.left);
                }

                if (node.right != null) {
                    queue.offer(node.right);
                }
            }

        }
    }

    public static void main(String[] args) {
        Node root = new Node(1);
        root.left = new Node(2);
        root.left.left = new Node(4);
        root.left.right = new Node(5);
        root.right = new Node(3);
        root.right.left = new Node(6);
        root.right.right = new Node(7);

        bfs(root);
    }

}