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

레벨에 따라 노드를 출력해보자

class Node {
    int data;   // 노드의 값(Node 객체 주소)를 저장하는 인스턴스 변수
    Node lt, rt;    // 노드의 child node의 값(객체 주소)를 저장하는 인스턴스 변수
    public Node(int val) {  // Node 생성자
        data = val;
        lt=rt=null;     // null로 초기화
    }
}
public class Main {
    Node root;  // 노드 객체 - 참조변수
    public void BFS(Node root) {
        Queue<Node> Q = new LinkedList<>(); // 레벨 차원에서 데이터를 가져와야하기 때문에 선입선출 자료구조 Queue 사용
        Q.offer(root);  //  1 저장
        int L = 1;  // 첫번째 레벨임을 선언

        while (!Q.isEmpty()) {  // Q가 비워지면 반복문 멈춤
            int len = Q.size(); 
            System.out.print(L+ " : ");
            for (int i=0; i<len; i++) {     // Queue에 들어있는 root를 차례대로 꺼내기 위한 반복문
                Node current = Q.poll();    // 현재의 루트 꺼내기
                System.out.print(current.data + " ");   // 현재의 루트값 출력
                if (current.lt != null) {
                    Q.offer(current.lt);    // 현재 루트의 lt값이 존재하면 Queue에 담기
                }
                if (current.rt != null){
                    Q.offer(current.rt);    // 현재 루트의 rt값이 존재하면 Queue에 담기
                }
            }
            L++;    // 레벨 더하기
            System.out.println();   // 줄바꿈
        }
    }

    public static void main(String[] args) {
        Main tree = new Main();
        // 7개의 Node 객체 생성
        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);
    }
}

루트 노드의 값을 변경해서 사용하지 말고,

현재의 노드 값을 변수에 담아서 사용하기 ⭐️