위와 같은 완전 이진트리를 배열로 구성해 BFS, DFS를 해보겠습니다.
BFS(너비우선탐색 )
루트 노드 혹은 시작하는 노드에서 자식 노드들을 먼저 모두 차례로 방문한 후에,
방문했던 자식 노드들을 기준으로 하여 다시 해당 노드들의 자식 노드들을 차례로 방문하는 방식이다.
BFS는 트리나 그래프에 적용할수 있다. 보통은 그래프에 적용해서 사용한다.
사실 트리도 그래프의 일종이기도 한데, 그냥 트리도 연습할겸
완전이진트리를 배열로 구현해서 bfs를 적용해보는 코드를 살펴보자.
완전이진트리를 선택한 이유는 완전이진트리를 배열로 나타낼때
자식노드에서 부모노드 접근할때는 인덱스 / 2
부모노드에서 자식노드에 접근할때는 인덱스2, 인덱스2+1 을 손쉽게 이용해먹을수 있기 때문이다.
완전이진트리를 BFS 해보자.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
class Complete_Binary_Tree {
// 완전 이진 트리
private char[] nodes;
private int lastIndex;
public Complete_Binary_Tree(int size) {
nodes = new char[size + 1];
lastIndex = 0;
}
public void add(char c) {
nodes[++lastIndex] = c;
}
public void bfs_print() {
bfs(1);
}
private void bfs(int idx) {
Queue<Integer> queue = new LinkedList<Integer>();
queue.offer(idx);
while(!queue.isEmpty()) {
int qsize = queue.size();
while(--qsize >= 0) {
int curridx = queue.poll();
System.out.print(nodes[curridx] + " ");
if(curridx*2 <= lastIndex)
queue.offer(curridx*2);
if((curridx*2+1) <= lastIndex)
queue.offer(curridx*2 + 1);
}
System.out.println();
}
}
}
public class BFS {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
System.out.print("완전이진트리의 사이즈를 입력해주세요 : ");
int size = Integer.parseInt(br.readLine());
Complete_Binary_Tree tree = new Complete_Binary_Tree(size);
System.out.print("이진트리의 각 노드들을 입력해주세요 : ");
String[] strarr = br.readLine().split(" ");
for (int i = 0; i < size; i++) {
tree.add(strarr[i].charAt(0));
}
tree.bfs_print();
}
}
DFS(깊이 우선 탐색)
루트 노드, 시작하는 노드에서 출발하여 한 방향으로 최대한 깊게 탐색하다가 다 탐색하면 다시 올라와서 옆의 브랜치로 가서 또 최대한 깊게 탐색하고 이런 방식을 반복하여 결국 그래프나 트리내의 모든 원소를 다 탐색하는 방법
구현에는 스택이나 재귀를 사용한다.
먼저 완전이진트리로 깊이 우선탐색을 해보겠다.
완전이진트리를 DFS 해보자.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
class Complete_Binarytree {
// 완전 이진 트리
private char[] nodes;
private int lastIndex;
public Complete_Binarytree(int size) {
nodes = new char[size + 1];
lastIndex = 0;
}
public void add(char c) {
nodes[++lastIndex] = c;
}
public void bfs_print() {
bfs(1);
}
private void bfs(int idx) {
Queue<Integer> queue = new LinkedList<Integer>();
queue.offer(idx);
while(!queue.isEmpty()) {
int qsize = queue.size();
while(--qsize >= 0) {
int curridx = queue.poll();
System.out.print(nodes[curridx] + " ");
if(curridx*2 <= lastIndex)
queue.offer(curridx*2);
if((curridx*2+1) <= lastIndex)
queue.offer(curridx*2 + 1);
}
System.out.println();
}
}
///////////////// DFS 추가한 부분/////////////////////
public void dfs_print() {
dfs(1);
}
private void dfs(int idx) {
if(idx > lastIndex) return;
System.out.print(nodes[idx] + " ");
dfs(2*idx);
dfs(2*idx+1);
}
////////////////////////////////////////////////////
}
public class DFS {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
System.out.print("완전이진트리의 사이즈를 입력해주세요 : ");
int size = Integer.parseInt(br.readLine());
Complete_Binarytree tree = new Complete_Binarytree(size);
System.out.print("이진트리의 각 노드들을 입력해주세요 : ");
String[] strarr = br.readLine().split(" ");
for (int i = 0; i < size; i++) {
tree.add(strarr[i].charAt(0));
}
tree.dfs_print();
}
}
BFS보다 훨씬 간단하다.
일단 완전이진트리에서 루트 노드 하나 선택한다음
그 다음 왼쪽자식 노드 오른쪽 자식노드로 계속 재귀를 돌리면 된다.
위 BFS코드에 DFS 처리 부분만 추가하였다.
지금까지 한것은 전위 순회 DFS이다.
이것을 중위와 후위순회로도 나태내보면
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
class Complete_Binarytree {
// 완전 이진 트리
private char[] nodes;
private int lastIndex;
public Complete_Binarytree(int size) {
nodes = new char[size + 1];
lastIndex = 0;
}
public void add(char c) {
nodes[++lastIndex] = c;
}
public void bfs_print() {
bfs(1);
}
private void bfs(int idx) {
Queue<Integer> queue = new LinkedList<Integer>();
queue.offer(idx);
while(!queue.isEmpty()) {
int qsize = queue.size();
while(--qsize >= 0) {
int curridx = queue.poll();
System.out.print(nodes[curridx] + " ");
if(curridx*2 <= lastIndex)
queue.offer(curridx*2);
if((curridx*2+1) <= lastIndex)
queue.offer(curridx*2 + 1);
}
System.out.println();
}
}
public void dfs_print() {
dfs(1);
}
public void dfs_inorder() {
dfs_inorder(1);
}
public void dfs_postorder() {
dfs_postorder(1);
}
private void dfs(int idx) {
if(idx > lastIndex) return;
System.out.print(nodes[idx] + " ");
dfs(2*idx);
dfs(2*idx+1);
}
private void dfs_inorder(int idx) {
if(idx > lastIndex) return;
dfs_inorder(2*idx);
System.out.print(nodes[idx] + " ");
dfs_inorder(2*idx+1);
}
private void dfs_postorder(int idx) {
if(idx > lastIndex) return;
dfs_postorder(2*idx);
dfs(2*idx+1);
System.out.print(nodes[idx] + " ");
}
}
public class DFS {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
System.out.print("완전이진트리의 사이즈를 입력해주세요 : ");
int size = Integer.parseInt(br.readLine());
Complete_Binarytree tree = new Complete_Binarytree(size);
System.out.print("이진트리의 각 노드들을 입력해주세요 : ");
String[] strarr = br.readLine().split(" ");
for (int i = 0; i < size; i++) {
tree.add(strarr[i].charAt(0));
}
System.out.println("전위순회 DFS");
tree.dfs_print();
System.out.println("\n중위순회DFS");
tree.dfs_inorder();
System.out.println("\n후위순회DFS");
tree.dfs_postorder();
}
}
다음과 같다.
마지막으로 재귀대신 stack을 이용해서 dfs를 할 수 도 있다.
코드가 쓸데없이 길어져서 stack을 이용한 dfs 부분의 코드만 올린다.
private void dfs_stack(int idx) {
Stack<Integer> stack = new Stack<Integer>();
stack.push(idx);
while(!stack.isEmpty()) {
int curr = stack.pop();
System.out.print(nodes[curr] + " ");
if(curr*2+1 <= lastIndex)
stack.push(curr*2+1);
if(curr*2 <= lastIndex)
stack.push(curr*2);
}
}
public void dfs_stack() {
dfs_stack(1);
}
현명한개발자가되자