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

Stack을 사용하는 DFS(깊이우선탐색)과 다르게 BFS(넓이우선탐색)은 Queue를 사용하며 각 노드 위치에따라 Level을 정하여 탐색한다.

 

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) {
		Queue<Node> Q = new LinkedList<>();
		Q.offer(root);
		int Level = 0;
		while(!Q.isEmpty()) {
			 int len = Q.size();
			 System.out.print(Level + " : ");
			 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);
				 }
			 }
			 Level++;
			 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);
	
	}
}