Q. 개념

---

아래 그림과 같은 이진트리를 레벨탐색 연습하세요.

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

전략

• 0레벨인 root를 시작으로 같은 레벨을 다 탐색하고 다음 레벨을 탐색
• 레벨은 root로부터 거치는 간선의 갯수(거리)
• (레벨0 : 1) -> (레벨1 : 2 -> 3) -> (레벨2 : 4 -> 5 -> 6 -> 7)
• 큐를 사용하여 레벨탐색

정답

import java.util.*;
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.add(root);
        int L=0; // root노드의 레벨은 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.add(cur.lt);
                if(cur.rt!=null) Q.add(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);
    }
}