[백준] 1991 트리 순회(자바/java)

문제

- 문제 출처 : https://www.acmicpc.net/problem/1991

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

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

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

가 된다.

입력

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

출력

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

---

루트 - 왼쪽자식 - 오른쪽자식 구조가 분명하고 그 구조대로 입력을 받기 때문에 

먼저 노드 클래스를 정의하였다.

 

class Node {
	String data;
	String lt, rt;

	public Node(String val) {
		this.data = val;
		lt = rt = null;
	}

}

 

그리고 전위순회, 중위순회, 후위순회는 각각의 메소드 내에서 출력하는 코드를 어디에 두느냐에 따라 나뉜다.

public static void preOrder(String data) {

		if (tree.get(data) == null) {
			return;
		} else {
			System.out.print(tree.get(data).data);
			preOrder(tree.get(data).lt);
			preOrder(tree.get(data).rt);

		}

	}

	public static void inOrder(String data) {

		if (tree.get(data) == null) {
			return;
		} else {
			inOrder(tree.get(data).lt);
			System.out.print(tree.get(data).data);
			inOrder(tree.get(data).rt);

		}

	}

	public static void postOrder(String data) {

		if (tree.get(data) == null) {
			return;
		} else {
			postOrder(tree.get(data).lt);
			postOrder(tree.get(data).rt);
			System.out.print(tree.get(data).data);

		}

	}

 

 

<전체 코드>

 

package tree;

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

class Node {
	String data;
	String lt, rt;

	public Node(String val) {
		this.data = val;
		lt = rt = null;
	}

}

public class Bj1991_트리순회 {
	private static int N;
	private static Map<String, Node> tree;

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());

		tree = new HashMap<String, Node>();
		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			String root = st.nextToken();
			String left = st.nextToken();
			String right = st.nextToken();

			Node node = new Node(root);
			node.lt = left;
			node.rt = right;

			tree.put(node.data, node);

		}

		preOrder("A");
		System.out.println();
		inOrder("A");
		System.out.println();
		postOrder("A");

	}

	public static void preOrder(String data) {

		if (tree.get(data) == null) {
			return;
		} else {
			System.out.print(tree.get(data).data);
			preOrder(tree.get(data).lt);
			preOrder(tree.get(data).rt);

		}

	}

	public static void inOrder(String data) {

		if (tree.get(data) == null) {
			return;
		} else {
			inOrder(tree.get(data).lt);
			System.out.print(tree.get(data).data);
			inOrder(tree.get(data).rt);

		}

	}

	public static void postOrder(String data) {

		if (tree.get(data) == null) {
			return;
		} else {
			postOrder(tree.get(data).lt);
			postOrder(tree.get(data).rt);
			System.out.print(tree.get(data).data);

		}

	}

}