[JAVA] 자바 이진트리 레벨탐색(BFS : Breadth-First Search)

 

이진트리의 레벨탐색은 루트 노드(levele 0)부터

루트 노드로 부터 한 칸 떨어져 있는 노드(level 1)

루트 노드로 부터 두 칸 떨어져 있는 노드(level 2)들을 순차적으로 탐색하는 것이다.

그림에서는 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 순서로 탐색을 한다

 

 

 

코드

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 BFS {
    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) {
        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);
    }
}

Q에서 각 level size만큼 노드를 poll하여 하나씩 출력하면서 해당 노드의 자식 노드를 offer해주는 방식이다.

자식 노드가 출력될 때에는 level 값인 L을 증가시켜서 출력해준다.

 

 

 

결과

 

 

 

 

출처 : 인프런 자바 알고리즘 문제풀이 입문 : 코딩테스트 대비