이진트리 레벨탐색

01 May 2023 in Algorithm on Java, Coding, Test

문제

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

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

해결방법

• BFS 너비 우선 탐색은, 같은 레벨의 모든 노드를 방문하여야 다음 레벨로 넘어갈 수 있다.
• 큐를 이용하여 자식 체크 시, 큐에 전부 넣고 체크 후 다시 빼는 방식을 이용한다.

코드

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) {
        // BFS 너비 우선 탐색은 큐를 이용해 진행한다.
        Queue<Node> Q = new LinkedList<>();
        Q.add(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.add(cur.lt);
                if (cur.rt != null) Q.add(cur.rt);
            }
            // 레벨을 증가 시킨다.
            L++;
            System.out.println();
        }
    }

    public static void main(String args[]) {
        Main.Main tree = new Main.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);
    }
}