[자료구조] 이진 트리 레벨 탐색 (BFS : Breath-First-Search)

 

 

너비 우선 탐색 (BFS)

• 루트 노드에서 시작해서 인접한 노드를 먼저 탐색하는 방법
• 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다.
• 깊게(deep) 탐색하기 전에 넓게(wide) 탐색하는 것이다.
• 사용 경우
  • 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 사용한다.
• BFS는 재귀적으로 동작하지 않는다.
• BFS는 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 자료 구조인 큐(Queue)를 사용한다.
• 그래프 탐색인 경우 어떤 노드를 방문했는지 여부를 반드시 검사해야 한다.

 

 

🔍 이진 트리 순회

 

• 레벨 탐색 순회 출력 : 1 2 3 4 5 6 7
  • 같은 레벨끼리 출력한다.

 

💡 이진 트리 만들기

public  class Solution {
    public static void main (String[] args) {    
    	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);
    }
    
    static class Node {
    	int data;
    	Node lt, rt;
    	
    	Node(int data) {
    		this.data = data;
    		lt = rt = null;
    	}
    }
}

 

 

🔍 레벨 탐색 순회

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

public  class Solution {
    public static void main (String[] args) {    
    	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);
    }
    
    static class Node {
    	int data;
    	Node lt, rt;
    	
    	Node(int data) {
    		this.data = data;
    		lt = rt = null;
    	}
    }
    
    static void BFS(Node root) {
    	Queue<Node> queue = new LinkedList<>();
    	queue.offer(root);
    	
    	int level = 0;  // 레벨
    	
    	while(!queue.isEmpty()) {
    		int size = queue.size();
    		System.out.print(level + " : ");
    		
    		for(int i=0; i<size; i++) {
    			Node cur = queue.poll();
    			System.out.print(cur.data + " ");
    			
    			if(cur.lt != null) queue.offer(cur.lt);
    			if(cur.rt != null) queue.offer(cur.rt);
    		}
    		
    		level++;
    		System.out.println();
    	}
    	
    	
    	
    }
    
    
}

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

 

🧷 그림으로 이해하기

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

🔍 Tree 말단 노드까지의 가장 짧은 경로

 

 

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

public class Solution {

	public static void main(String[] args){
		
    	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);
	  
    	BFS(root);
    	
	}
	
	static class Node {
		
		int data;
		
		Node rt;
		Node lt;
	  
		Node(int data) {
			this.data = data;
		}
  }
  

  static void BFS(Node root) {
	  int level = 0;
	  
	  Queue<Node> queue = new LinkedList<>();
	  queue.offer(root);
	  
	  while(!queue.isEmpty()) {
		  
		  int size = queue.size();
		  
		  for(int i=0; i<size; i++) {
			  Node cur = queue.poll();
			  if(cur.lt==null && cur.rt==null) {
				  System.out.println(level + ", " + cur.data);
				  return;
			  }
			  
			  if(cur.lt !=null) queue.offer(cur.lt);
			  if(cur.rt !=null) queue.offer(cur.rt);
			  
		  }
		  
		  level++;
		  
	  }  // end of while
	  
	  
  }
  
  
}

1, 3

• 말단 노드 중 가장 짧은 경로는 3번 째 노드이다.

 

 

---

👀 참고 자료

https://gmlwjd9405.github.io/2018/08/15/algorithm-bfs.html

[알고리즘] 너비 우선 탐색(BFS)이란 - Heee's Development Blog