https://www.acmicpc.net/problem/1991

문제

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

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

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

입력

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

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

출력

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

ABDCEFG
DBAECFG
DBEGFCA

풀이

이 문제를 풀기 위해서는 우선 트리를 구현할 수 있어야 한다.
트리를 구현하는 방법은 여러 가지가 있겠지만, 여기에서는 Node클래스와 Tree클래스로 구현해 주었다.

이진 트리가 아니기 때문에 루트가 아닌 노드를 추가로 연결하기 위해서는 노드를 탐색하는 과정이 필요한데, 이건 어쩔 수 없이 일일히 탐색할 수밖에 없다...

다행히도 문제 조건상 트리에서 노드 이름(값)은 반드시 알파벳 순서대로 주어지기 때문에 루트와 연결되지 않은 서브 트리가 만들어졌다가 그 서브 트리를 루트 트리와 연결해야 한다던가... 하는 일은 일어나지 않는다.

      a
    g   d
  b  h    f
c  e
// 이런 경우는 존재하지 않음

      a
    b   c
  d  e    f
g  h
// 반드시 이런 순서로 이름이 매겨진다는 뜻

전체 코드

import java.util.Scanner;

class Node {
	char data;
	Node left;
	Node right;

	Node(char data) {
		this.data = data;
	}
}

class Tree {
	public Node root;

	// 첫 노드 생성
	public void createNode(char data, char leftData, char rightData) {
		if (root == null) {
			root = new Node(data);
			root.left = new Node(leftData);
			root.right = new Node(rightData);
		} else // 루트가 null이 아니면 탐색 시작
			searchNode(root, data, leftData, rightData);
	}

	// 노드 탐색
	public void searchNode(Node node, char data, char leftData, char rightData) {
		if (node == null) // 노드가 없을 경우 return
			return;
		if (node.data == data) { // 노드를 찾은 경우
			node.left = new Node(leftData);
			node.right = new Node(rightData);
		} else {
			searchNode(node.left, data, leftData, rightData); // 왼쪽 탐색
			searchNode(node.right, data, leftData, rightData); // 오른쪽 탐색
		}
	}

	// 전위 순회: 루트->왼쪽->오른쪽
	public void preorder(Node node) {
		if (node.data != '.') {
			System.out.print(node.data);
			preorder(node.left);
			preorder(node.right);
		}
	}

	// 중위 순회: 왼쪽->루트->오른쪽
	public void inorder(Node node) {
		if (node.data != '.') {
			inorder(node.left);
			System.out.print(node.data);
			inorder(node.right);
		}
	}

	// 후위 순회: 왼쪽->오른쪽->루트
	public void postorder(Node node) {
		if (node.data != '.') {
			postorder(node.left);
			postorder(node.right);
			System.out.print(node.data);
		}
	}
}

public class BJ_1991 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		Tree t = new Tree();

		int n = sc.nextInt();
		for (int i = 0; i < n; i++) {
			char data = sc.next().charAt(0);
			char leftData = sc.next().charAt(0);
			char rightData = sc.next().charAt(0);
			t.createNode(data, leftData, rightData);
		}

		t.preorder(t.root);
		System.out.println();
		t.inorder(t.root);
		System.out.println();
		t.postorder(t.root);
	}

}

지금 보니까 그냥 .인 경우를 검사해서 빈 것은 아예 null값으로 지정해 둘 걸 그랬나... 이런 식으로.

if (node.data == data) { // 노드를 찾은 경우
	if (leftData != '.') node.left = new Node(leftData);
	if (rightData != '.') node.right = new Node(rightData);
} 

+

문제를 풀면서 자바의 객체 개념에 대해 좀 더 익숙해질 수 있었던 것 같다. 객체에서 다른 객체를 이용한다는 게 어색했지만 그래도 어떻게 잘 해낸 것 같다!