트리 순회

문제

1991번: 트리 순회

문제 설명

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

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

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

가 된다.

제한 사항

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	128 MB	49279	31768	24464	67.078%

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

입출력 예

입력	출력
7	ABDCEFG
A B C	DBAECFG
B D .	DBEGFCA
C E F
E . .
F . G
D . .
G . .

제출 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class one1991 {
    static class Node {
        char value;
        Node left;
        Node right;

        Node(char value, Node left, Node right) {
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }

    private int size;
    private char[] tree;
    private Node head = new Node('A', null, null);

    public void solution() throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        size = Integer.parseInt(reader.readLine());
        tree = new char[size];

        for (int i = 0; i < size; i++) {
            StringTokenizer treeToken = new StringTokenizer(reader.readLine());

            char root = treeToken.nextToken().charAt(0);
            char left = treeToken.nextToken().charAt(0);
            char right = treeToken.nextToken().charAt(0);
            insertNode(head,root, left, right);

        }

        preOrder(head);
        System.out.println();
        inOrder(head);
        System.out.println();
        postOrder(head);
    }

    private void postOrder(Node head) {
        if (head == null) return;
        postOrder(head.left);
        postOrder(head.right);
        System.out.printf("%c", head.value);
    }

    private void inOrder(Node head) {
        if (head == null) return;
        inOrder(head.left);
        System.out.printf("%c", head.value);
        inOrder(head.right);
    }

    private void preOrder(Node head) {
        if (head == null) return;
        // root -> left -> right
        System.out.printf("%c", head.value);
        preOrder(head.left);
        preOrder(head.right);
    }

    private void insertNode(Node head, char root, char left, char right) {
        if (head.value == root) {
            head.left = (left == '.') ? null : new Node(left, null, null);
            head.right = (right == '.') ? null : new Node(right, null, null);
        }
        else {
            if (head.left != null) insertNode(head.left, root, left, right);
            if (head.right != null) insertNode(head.right, root, left, right);
        }
    }

    public static void main(String[] args) throws IOException {
        new one1991().solution();
    }
}