[BFS] 7. 이진트리 레벨탐색

BFS의 개념을 위한 문제이다.

깊이 우선 탐색이었던 DFS와 다르게 BFS는 각 층을 레벨로 두어서 0 레벨부터 전 부 탐색하고 그 다음 레벨을 탐색하는 형태이다.

 

 

 

DFS에서 사용했던 Node 트리를 활용해서 BFS를 구현해보았다.

 

이때는 Queue를 활용해서 구현을 했는데, 각 층의 값은 poll 해주고 그 다음 자식 노드는 offer 해주는 식으로 진행했다.

 

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

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


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

 

BFS 방식과 DFS 방식을 잘 기억해두자 ~!