백준 1991번 : 트리 순회

[레벨4]

 

· 문제

이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 프로그램을 작성하시오.

예를 들어 위와 같은 이진 트리가 입력되면,

• 전위 순회한 결과 : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 자식)
• 중위 순회한 결과 : DBAECFG // (왼쪽 자식) (루트) (오른쪽 자식)
• 후위 순회한 결과 : DBEGFCA // (왼쪽 자식) (오른쪽 자식) (루트)

가 된다.

 

· 입력

첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파벳 대문자로 매겨지며, 항상 A가 루트 노드가 된다. 자식 노드가 없는 경우에는 .으로 표현한다.

 

· 출력

첫째 줄에 전위 순회, 둘째 줄에 중위 순회, 셋째 줄에 후위 순회한 결과를 출력한다. 각 줄에 N개의 알파벳을 공백 없이 출력하면 된다.

 

· 풀이

import java.io.*;
import java.util.*;

public class Main {
	
	static class Node {
		int left;
		int right;

		public Node(int left, int right) {
			this.left = left;
			this.right = right;
		}
	}

	static List<Node>[] list;
	static StringBuilder sb = new StringBuilder();

	public static void main(String[] args) throws Exception {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		
		int n = Integer.parseInt(br.readLine());

		list = new ArrayList[n + 1];
		
		for (int i = 1; i < n + 1; i++) {
			list[i] = new ArrayList<>();
		}

		for (int i = 1; i < n + 1; i++) {
			String[] line = br.readLine().split(" ");
			int data = line[0].charAt(0) - 'A' + 1;
			int left = line[1].charAt(0) - 'A' + 1;
			int right = line[2].charAt(0) - 'A' + 1;
			list[data].add(new Node(left, right));
		}

		pre(1);
		sb.append("\n");
		in(1);
		sb.append("\n");
		post(1);
		System.out.println(sb.toString());

	}

	// 전위 순회.
	static void pre(int start) {
		for (Node node : list[start]) {
			int l = node.left;
			int r = node.right;

			sb.append((char) (start + 'A' - 1));
			if (l != -18)
				pre(l);
			if (r != -18)
				pre(r);
		}
	}

	// 중위 순회.
	static void in(int start) {
		for (Node node : list[start]) {
			int l = node.left;
			int r = node.right;

			if (l != -18)
				in(l);
			sb.append((char) (start + 'A' - 1));
			if (r != -18)
				in(r);
		}
	}

	// 후위 순회.
	static void post(int start) {
		for (Node node : list[start]) {
			int l = node.left;
			int r = node.right;

			if (l != -18)
				post(l);
			if (r != -18)
				post(r);
			sb.append((char) (start + 'A' - 1));
		}
	}
}