[Ch.07 - BFS] 01. 이진트리 순회 (+ 넓이우선탐색 BFS)

1. 이진트리 순회 (넓이우선탐색 : 레벨탐색)

Breadth First Search (BFS : 낮은 레벨부터 탐색)

-> 현재 위치에서의 최단 거리 탐색에 사용

 

//큐에 넣어서, 낮은 레벨부터 출력
Queue<Node> Q = new LinkedList<>();
Q.offer(root);
int L=0;

while(!Q.isEmpty()) {
//비어있으면 거짓, 비어있지 않으면 참 -> 비어있을 때까지 반복

 ~
}

L++;

1. 큐의 원소 개수를 위한 변수 설정
2. 현재 노드 출력
3. 연결된 자식들 넣기
4. 현재 노드의 왼쪽 노드가 존재한다면, 왼쪽 노드 삽입
5. 현재 노드의 오른쪽 노드가 존재한다면, 오른쪽 노드 삽입

 

 

큐 그리기 : 1 넣기 -> 1과 연결된 2,3 넣기 -> 2와 연결된 4,5 넣기 -> 3과 연결된 6,7 ->순서대로 poll
출력 : 0레벨 : 1, 1레벨: 2,3  ->3레벨 : 4, 5, 6, 7

---

 

package dfsbfs.ch07;

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

//BFS
//넓이 우선 탐색 : 레벨탐색 Level Order
//큐를 이용한 레벨 탐색
//0레벨 -> 1레벨 -> 2레벨 [방문하기 위해 필요한 간선의 개수]
//현재 위치에서의 최단 거리 탐색에 사용
//class Node{
//	int data;
//	Node lt, rt;
//	public Node(int val) {
//		data=val;
//		lt=rt=null;
//	}
//}
public class Dfsbfs03 {
	Node root;
	public void BFS(Node root) {
		Queue<Node> Q = new LinkedList<>();
		Q.offer(root);
		//add가능
		int L=0;
		//레벨 변수 생성
		while(!Q.isEmpty()) {
			//비어있으면 거짓, 비어있지 않으면 참 -> 비어있을 때까지 반복
			int len=Q.size();
			//Q의 원소개수 변수 설정 -> 루트노드만 들어올경우 :1
			System.out.print(L+" : ");
			for(int i=0;i<len;i++) {
				//len: 1 ->2 ->  4
				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);
					//현재 노드의 오른쪽 노드가 존재한다면, 오른쪽 노드 삽입
				}
				
				else {
					//현재 노드의 왼쪽 노드가 존재하지 않는다면, 말단노드
				}
				//레벨 증가
				
			}
			L++;
			System.out.println();
			System.out.println("len : "+len);

			//큐 그리기 : 1 넣기 -> 1과 연결된 2,3 넣기 -> 2와 연결된 4,5 넣기 -> 3과 연결된 6,7 ->순서대로 poll
			//출력 : 0레벨 : 1, 1레벨: 2,3  ->3레벨 : 4, 5, 6, 7
			
		}
		
	}
	
	public static void main(String[] args) {
		Dfsbfs03 tree = new Dfsbfs03();
		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);
		//루트 노드를 BFS에 인자로 전달 [tree.root는 루트노드를 가리키는 주소]
		//root.data=1
	}
	

}