자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비(BFS_이진트리 레벨탐색(BFS : Breadth-First Search))

 

 

7. 이진트리 레벨탐색(BFS : Breadth-First Search)

 

이진트리 순회 (넓이 우선 탐색 : 레벨 탐색)

레벨 탐색 순회 출력 : 1 2 3 4 5 6 7

 

레벨 순으로 탐색합니다.

상태트리로 보자면, 루트 출발점에서 한번만에 갈 수 있는 노드들(간선)을 방문해보고, 2번만에 갈 수 있는 노드들 다 방문해보고 이런걸 BFS라고 합니다.

 

최단 거리 탐색에서 쓰인다.

 

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

class Node {
    int data;
    Node lt, rt;
    public Node(int val) {
        data = val;
        lt=rt=null;
    }
}
public 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+ " "); // Q에 어떤 원소가 담겨져 있는지
                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);
    }


}

0 : 1 
1 : 2 3 
2 : 4 5 6 7

 

1. 제일 먼저 스타트 지점인 1번 넣고, 1을 poll해서 출력한다.  | 현재  Queue : 1
2. 1번이랑 연관된 2, 3번을 Queue에 넣는다. | 현재  Queue : 2, 3
3. 2를 poll하고, 2랑 관련된 4,5를  Queue에 넣는다.  | 현재  Queue : 3, 4, 5
4. 3를 poll하고, 3랑 관련된 6,7을  Queue에 넣는다. | 현재  Queue : 4, 5, 6, 7
5. 이제 연관된거 없으니까 다 poll해서 출력한다. | 현재  Queue : 

 

현재 이런 걸 완전 풀 이진 트리(= 꽉찬 이진 트리)라고 한다.