백준1991_트리

문제

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

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

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

가 된다.

입력

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

출력

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

예제 입력 

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

예제 출력 

ABDCEFG
DBAECFG
DBEGFCA

[코드]

import java.util.Scanner;
 
public class Main {
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Tree Root[] = new Tree[n];
        Tree Left[] = new Tree[n];
        Tree Right[] = new Tree[n];
 
        for (int i = 0; i < n; i++) {
            Root[i] = new Tree();
            Left[i] = new Tree();
            Right[i] = new Tree();
        }
 
        for (int i = 0; i < n; i++) {
            String root = sc.next();
            String left = sc.next();
            String right = sc.next();
 
            int idx = 0;
            for (int j = 0; j < i; j++) {
                if (Left[j].val.equals(root)) {
                    idx = Left[j].depth;
                    break;
                }
                if (Right[j].val.equals(root)) {
                    idx = Right[j].depth;
                    break;
                }
                if (j == n - 1) {
 
                }
            }
            Root[i].setValue(idx, root);
            Left[i].setValue(idx + 1, left);
            Right[i].setValue(idx + 1, right);
        }
 
        travelPreorder(Root, Left, Right, 0);
        System.out.println();
        travelInorder(Root, Left, Right, 0);
        System.out.println();
        travelPostorder(Root, Left, Right, 0);
    }
 
    public static void travelPreorder(Tree Root[], Tree Left[], Tree Right[],
            int idx) {
 
        System.out.print(Root[idx].val);
        if (!Left[idx].equals(".")) {
            for (int i = 0; i < Left.length; i++) {
                if (Left[idx].val.equals(Root[i].val)) {
                    travelPreorder(Root, Left, Right, i);
                    break;
                }
            }
        }
        if (!Right[idx].equals(".")) {
            for (int i = 0; i < Right.length; i++) {
                if (Right[idx].val.equals(Root[i].val)) {
                    travelPreorder(Root, Left, Right, i);
                    break;
                }
            }
        }
 
    }
 
    public static void travelInorder(Tree Root[], Tree Left[], Tree Right[],
            int idx) {
        if (!Left[idx].equals(".")) {
            for (int i = 0; i < Left.length; i++) {
                if (Left[idx].val.equals(Root[i].val)) {
 
                    travelInorder(Root, Left, Right, i);
                    break;
                }
            }
        }
        System.out.print(Root[idx].val);
        if (!Right[idx].equals(".")) {
            for (int i = 0; i < Right.length; i++) {
                if (Right[idx].val.equals(Root[i].val)) {
                    travelInorder(Root, Left, Right, i);
                    break;
                }
            }
        }
    }
 
    public static void travelPostorder(Tree Root[], Tree Left[], Tree Right[],
            int idx) {
 
        if (!Left[idx].equals(".")) {
            for (int i = 0; i < Left.length; i++) {
                if (Left[idx].val.equals(Root[i].val)) {
                    travelPostorder(Root, Left, Right, i);
                    break;
                }
            }
        }
        if (!Right[idx].equals(".")) {
            for (int i = 0; i < Right.length; i++) {
                if (Right[idx].val.equals(Root[i].val)) {
                    travelPostorder(Root, Left, Right, i);
                    break;
                }
            }
        }
        System.out.print(Root[idx].val);
    }
}
 
class Tree {
 
    int depth;
    String val;
 
    public Tree() {
 
    }
 
    public void setValue(int depth, String val) {
        this.depth = depth;
        this.val = val;
    }
 
}

트리의 depth 를 쓸 일이 있을까 하고 만들어봤는데 안 썼다.

굳이 Tree 클래스를 만들지 않고 String 배열로 만들었어도 됐을 뻔 했다.

[알고리즘]

그냥 중위, 후위, 전위 개념을 생각해서 짰다.

세 개의 배열을 각각 만들고 ( 루트, 왼쪽, 오른쪽 자식 )

배열안에 입력받은 내용들을 각각 집어넣었다. 노드의 수가 26개가 한계라고 나와있어서 재귀호출로 풀어도 StackFlow 에러가 나지 않을 것 같아 재귀로 풀었다.

+

트리를 한번도 구현해본 적이 없어서 계속 트리 구조를 만들어주다가 지웠다가 넣었다가 삭제했다가 했다.

도데체 노드를 하나하나 연결해줘야 할까 어떻게 해야할까 고민하느라고 오래 걸렸는데 단순하게 푸는게 제일 최고인 것 같다. 물론 이건 알고리즘 문제고 풀어야 하는거니까 그거에 맞춰서 배열에 끼워 넣었지만, 이참에 그냥 트리를 직접 구현해보는 것도 나쁘진 않은 것 같다.