[Baekjoon] 1991번 트리 순회 (Java)

예제 입력

7
A B C
B D .
C E F
E . .
F . G
D . .
G . .

예제 출력

ABDCEFG
DBAECFG
DBEGFCA

 

 

package Q1991;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;

class Node{
	String node;
	String left;
	String right;
	
	public Node(String[] str){	// 배열이 들어올 때마다 자신과 왼쪽 자식, 오른쪽 자식 지정
		this.node = str[0];
		this.left = str[1];
		this.right = str[2];
	}
}

public class Main {
	static int num = 0;
	static HashMap<String, Node> map;
	static ArrayList<String> arr = new ArrayList<String>();
	public static void main(String[] args)  throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		num = Integer.parseInt(br.readLine());
		String[] str = new String[3];
		map = new HashMap<String, Node>();
		for(int i = 0; i < num; i++) {
			str = br.readLine().split(" "); 	// 입력 받은 값 줄 별로 split해서 str[i]에 저장
			map.put(str[0], new Node(str));
		}

		// ------ 전위 ------ (루트 -> 왼쪽 -> 오른쪽)
		pre("A");			
		arr.removeAll(arr);
		System.out.println();
		// ------ 중위 ------ (왼쪽 -> 루트 -> 오른쪽)
		in("A");
		arr.removeAll(arr);
		System.out.println();
		// ------ 후위 ------ (왼쪽 -> 오른쪽 -> 루트)
		post("A");
		System.out.println("A");
	}	
	public static void pre(String parent) {
		String left = map.get(parent).left;
		String right = map.get(parent).right;
		if(!arr.contains(parent)) {		// 출력된적 없는 루트 노드 출력
			System.out.print(parent);
			arr.add(parent);
		}
		if(!left.equals(".")) {			// 왼쪽 자식이 있다면
			if(!arr.contains(left)) {	// 출력된적 없는 노드라면 출력하고 재귀
				System.out.print(left); arr.add(left); pre(left);
			}
		}else if(left.equals(".") && right.equals(".")){return;}	// 리프 노드라면 호출됐던 곳으로 되돌아감.
		if(!right.equals(".")) {		// 오른쪽 자식이 있다면
			if(!arr.contains(right)) {	// 출력된적 없는 노드라면 출력하고 재귀
				System.out.print(right); arr.add(right); pre(right);
			}
		}else {return;}					// 오른쪽 자식이 없다면 호출됐던 곳으로 되돌아감(부모 노드)
	}
	public static void in(String parent) {
		String left = map.get(parent).left;
		String right = map.get(parent).right;
		if(!left.equals(".")) {			// 왼쪽 자식이 존재한다면
			in(left);					// 재귀(가장 왼쪽부터 탐색해야 하기 때문)
			if(!arr.contains(parent)) {	
				System.out.print(parent);
				arr.add(parent);
			}
		}else if(left.equals(".")) {	// 왼쪽 자식이 존재하지 않는 경우
			if(!arr.contains(parent)) {	// 부모 노드가 출력된 적이 없다면 출력
				System.out.print(parent); arr.add(parent);
				if(!right.equals(".")) { in(right); }	// 오른쪽 자식이 존해하는 경우 재귀
				return;					// 아닌 경우 호출됐던 곳으로 되돌아감
			}			
		}
		if(!right.equals(".")) {		// 오른쪽 자식이 존재한다면 재귀
			in(right);
		}else if(right.equals(".")) {	// 오른쪽 자식이 존재하지 않고 부모 노드가 출력된적이 없다면 출력
			if(!arr.contains(parent)) { System.out.print(parent); arr.add(parent); }
			return;
		}
	}
	public static void post(String parent) {
		String left = map.get(parent).left;
		String right = map.get(parent).right;
		if(!left.equals(".")) {		// 왼쪽 자식이 존재하면 재귀(left)	-> 왼쪽 리프노드부터 탐색해야 하기 때문
			post(left);
			if(!arr.contains(left)) {
				System.out.print(left); arr.add(left);
			}
		}else if(left.equals(".") && !right.equals(".")) {	// 왼쪽 자식 존재 x, 오른쪽 자식 존재 o -> 재귀(right)
			post(right);
			if(!arr.contains(right)) {
				System.out.print(right); arr.add(right);
			}
		}else {return;}	
		
		if(!right.equals(".")) {	// 오른쪽 존재하면 재귀(right)
			post(right);
			if(!arr.contains(right)) {
				System.out.print(right); arr.add(right);
			}
		}else {return;}
	}
}