[BFS] 이진 트리 레벨 탐색

 

 

import java.util.*;
public class Main {

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

        bfs(root);
    }

    private static void bfs(Node node) {
        Queue<Node> q = new LinkedList<>();
        q.offer(node);

        int level = 0;
        
        while (!q.isEmpty()) {
            System.out.println("current level : " + level + " ");
            int size = q.size(); 
            // for 문에서 q.size()로 반복을 수행하면 q의 크기가 동적으로 변하기 때문에 size 변수에 담아둔다.

            for (int i = 0; i < size; i++) {
                Node poll = q.poll();
                System.out.print(poll.num + " ");
                if (poll.left != null) q.offer(poll.left);
                if (poll.right != null) q.offer(poll.right);
            }

            level++;
            System.out.println();
        }
    }

    private static class Node {
        int num;
        Node left;
        Node right;

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

 

 

private static void bfs(Node node) {
        Queue<Node> q = new LinkedList<>();
        q.offer(node);

        int level = 0;
        
        while (!q.isEmpty()) {
            System.out.println("current level : " + level + " ");
            int size = q.size();

            for (int i = 0; i < size; i++) {
                Node poll = q.poll();

                System.out.print(poll.num + " ");

                if (poll.left != null) q.offer(poll.left);
                if (poll.right != null) q.offer(poll.right);
            }

            level++;
            System.out.println();
        }
    }

 

 

1. BFS 수행 시 Q가 필요하다. 

LinkedList, ArrayDeque 중 ArrayDeque 구현체가 더 뛰어난 성능을 가진다.

 

2. while문을 수행하기 전 먼저 Q에 시작 노드를 넣는다.

BFS는 DFS와 달리 재귀 기반이 아니다.

 

3. int size = q.size()로 고정된 변수로 사이즈를 담아두지 않으면 for문을 수행하며 q의 크기가 가변적으로 변한다.

 

4. 인접 노드 확인

if (poll.left != null) q.offer(poll.left);
if (poll.right != null) q.offer(poll.right);

인접 노드 확인 후 방문할 곳이 있다면 방문 수행

레벨 탐색에서는 방문한 노드를 재방문하지 않기 때문에 방문 처리를 할 필요가 없다.

상황에 따라 Node 클래스의 필드로 boolean visited 를 두어야 할 때가 있다.