💡 이진트리 순회(BFS: Breadth-First Search, 넓이우선탐색, 레벨탐색)

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

 

 

 

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

 

 

---

 

문제 분석

BFS는 최단거리탐색에 쓰입니다.
큐를 사용합니다.

 

루트 - 레벨 0

루트에서 한 번만에 갈 수 있는 노드 - 레벨 1

루트에서 두 번만에 갈 수 있는 노드 - 레벨 2

...

 

 

레벨 0 다 탐색하고 레벨 1 다 탐색하고 레벨 2 다 탐색...

 

 

코드 구현

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){ 
    		// Node객체 저장하는 큐 선언
		Queue<Node> Q=new LinkedList<>();
		Q.add(root);
        	// L : Level
		int L=0;
        while(!Q.isEmpty()){
            // Q에 원소가 몇 개 들어가 있는가
            int len = Q.size();
            //System.out.print(L+" : ");
            for(int i=0; i<len; i++){
            	// Node형
                Node cur = Q.poll();
                // 한 레벨의 원소 출력 후 
                System.out.print(cur.data+" ");
                // 자식을 Q에 넣음, cur:현재노드, if(cur.lt!=null):말단 노드 거르기 위함
                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); 
    } 
}

 

특히 레벨을 이용해서 방문하는 방법을 잘 알아두어야 합니다.