[알고리즘]BFS - 이진트리 순회

* BFS(Breadth-First Search) - 넓이(너비)우선 탐색:  레벨 탐색

시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법이다.

더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 너비 우선 검색을 적용한다.

Queue를 사용해 레벨 순서대로 접근 가능하다.

 

* BFS VS DFS

 

 

이진트리 레벨탐색

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

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

public class Main { // BFS - 넓이 우선 탐색
	Node root;
	
	public void BFS(Node node) {
		Queue<Node> queue = new LinkedList<>();
		queue.offer(node);
		int level = 0;
		
		while(!queue.isEmpty()) {
        		int len = queue.size(); // 이거 주의! 안하면 len 계속 바뀜
			System.out.print("level" + level + " : ");
			for (int i=0; i<len; 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();
		}
	}

	public static void main(String[] args) {
		Main tree = new Main();
		tree.root = new Node(1); // 루트 : 0레벨
		tree.root.lt = new Node(2); // 1레벨
		tree.root.rt = new Node(3);
		tree.root.lt.lt = new Node(4); // 2레벨
		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); // 루트
	}

}

---

level0 : 1
level1 : 2 3
level2 : 4 5 6 7