[PS] 인프런 강의 - Tree 3. 이진트리 순회(넓이우선탐색 BFS : 레벨탐색)

 

문제

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

 

 

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

풀이

레벨에 따라 노드는 다음과 같이 나뉜다

 

0 : 1 
1 : 2 3 
2 : 4 5 6 7 

 

큐를 사용하여 푼다.

코드

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

class Node{
	int data;
	Node lt, rt;
	
	public Node(int val) {
		data = val;
		lt = rt = null;
	}
}

public class Main {

	//레벨 탐색
	public static 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) {
        Scanner in = new Scanner(System.in);
        Node 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);
    }
}