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

1. 문제

 

위 그림과 같은 이진트리를 레벨 탐색 연습하시오.

 

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

 

2. 나의 풀이

강의 보고 진행

 

3 - 1. 강의 풀이

트리 선언 후 

0, 1, 2 레벨의 트리들을 순회한다.

 

Q에 root 를 넣는다. (순회)

root를 Q에서 빼고 root.lt와 rt를 Q에 넣는다.

이를 반복한다.

 

 

3 - 2. 강의 코드

package BFS_DFS;
import java.util.*;

class Node{
    int data;
    Node lt;
    Node rt;

    Node(int value) {
        this.data = value;
    }
}

public class bfs07 {
    static Node root;

    public static void BFS(Node root) { //bfs로 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++) { //트리 수 만큼 q.poll하고 양 옆 트리를 Q에 다시 넣는다.
                Node next = q.poll();
                System.out.print(next.data +" ");
                if(next.lt!=null) q.offer(next.lt);
                if(next.rt!=null) q.offer(next.rt);
            }
            L++;
            System.out.println();
        }

    }

    public static void main(String[] args) {
        root = new Node(1);
        root.lt = new Node(2);
        root.rt = new Node(3);
        root.lt.lt = new Node(4);
        root.lt.rt = new Node(5);
        root.rt.lt = new Node(6);
        root.rt.rt = new Node(7);

        BFS(root);


    }
}

 

 

4. 얻어갈 점

코드 읽으면 문제될 게 없음