-
넓이 우선 탐색은 한줄씩 읽으며 내려간다.
레벨 순 탐색한다고 하는데
루트노드를 0레벨,
다음줄 1레벨(루트기준 노드 한번),
그 다음줄 2레벨(루트기준 노드 두번) ,,,
큐로 구현
1 들어갔다가
1 나오고 연결된 2 , 3 들어가고
2 나오고 연결된 4, 5가 뒤로 들어가고
3 나오고 연결된 6,7이 뒤로 들어가고
,,,
import java.util.LinkedList; import java.util.Queue; class Node7{ //이진트리(넓이우선) int data; Node7 lt,rt; public Node7(int val) { data=val; lt=rt=null; } } public class Tree7 { Node7 root; public void BFS(Node7 root) { Queue<Node7> Q = new LinkedList<>(); Q.offer(root); int L=0; while(!Q.isEmpty()) { int len = Q.size(); System.out.print(L +" : "); for(int i=0;i<len;i++) { Node7 cur = Q.poll(); System.out.print(cur.data+" "); if(cur.lt!=null) Q.offer(cur.lt); if(cur.rt!=null) Q.offer(cur.rt); } L++; System.out.println(); } } public static void main(String[] args) { Tree7 tree=new Tree7(); tree.root=new Node7(1); tree.root.lt=new Node7(2); tree.root.rt=new Node7(3); tree.root.lt.lt=new Node7(4); tree.root.lt.rt=new Node7(5); tree.root.rt.lt=new Node7(6); tree.root.rt.rt=new Node7(7); tree.BFS(tree.root); } }
'자바알고리즘' 카테고리의 다른 글
[262가지 문제로 정복하는 코딩 인터뷰 간단요약] 5장 배열(1) (0) 2022.11.26 [262가지 문제로 정복하는 코딩 인터뷰 간단요약] 4장 기본 자료형 (0) 2022.11.18 자바 이진트리 순회(1.DFS - 깊이 우선탐색) (0) 2021.09.04 재귀함수와 스택프레임 (0) 2021.09.03 정렬정리(선택정렬, 버블정렬 , 삽입정렬) (0) 2021.09.02 댓글