[BOJ] 백준 1991번 트리 순회 - JAVA 자바 풀이

접근법

트리 자료구조를 표현하기 위해 배열을 선언합니다. 배열의 타입은 Node[] 입니다.

트리의 각 노드를 표현하기 위해 왼쪽, 오른쪽 자식을 가리킬 수 있는 Node 클래스를 선언합니다.

'A' 'B' 'C' 등 각 Node의 값은 배열의 인덱스로 표현할 수 있습니다.

 

Node 클래스

class Node {
    int left; // 왼쪽 자식의 인덱스
    int right; // 오른쪽 자식의 인덱스

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

 

왼쪽 자식의 인덱스와 오른쪽 자식의 인덱스를 포함하는 Node 클래스를 생성했습니다.

Node 배열을 생성하고, 알파벳 A를 기준으로 인덱스 0부터 저장했습니다.

 

순회 재귀 메서드

public static void preorder(int idx) throws IOException {
    bw.write(idx + 'A');
    if(arr[idx].left != NONE) preorder(arr[idx].left);
    if(arr[idx].right != NONE) preorder(arr[idx].right);
}

public static void inorder(int idx) throws IOException {
    if(arr[idx].left != NONE) inorder(arr[idx].left);
    bw.write(idx + 'A');
    if(arr[idx].right != NONE) inorder(arr[idx].right);
}

public static void postorder(int idx) throws IOException {
    if(arr[idx].left != NONE) postorder(arr[idx].left);
    if(arr[idx].right != NONE) postorder(arr[idx].right);
    bw.write(idx + 'A');
}

 

• 전위 순회는 왼쪽, 오른쪽 자식을 탐색하기 전에 현재 노드의 idx를 출력합니다.
• 중위 순회는 왼쪽 자식을 탐색한 후 현재 노드의 idx를 출력하고, 그 다음에 오른쪽 자식을 탐색합니다.
• 후위 순회는 왼쪽, 오른쪽 자식을 탐색한 후 현재 노드의 idx를 출력합니다.

 

전체 코드

class Main {
    static Node[] arr;
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static final int NONE = -1; // 자식이 없는 경우

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        arr = new Node[N];

        while(N-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            int node = st.nextToken().charAt(0)-'A';

            char lft = st.nextToken().charAt(0);
            int left = lft == '.' ? NONE : lft-'A'; // '.' 이라면 자식이 없다고 표기

            char rgt = st.nextToken().charAt(0);
            int right = rgt == '.' ? NONE : rgt-'A';

            if(arr[node] == null)
                arr[node] = new Node(left, right);
        }

        preorder(0);
        bw.write('\n');
        inorder(0);
        bw.write('\n');
        postorder(0);

        bw.flush();
        bw.close();
    }

    public static void preorder(int idx) throws IOException {
        bw.write(idx + 'A');
        if(arr[idx].left != NONE) preorder(arr[idx].left);
        if(arr[idx].right != NONE) preorder(arr[idx].right);
    }
    public static void inorder(int idx) throws IOException {
        if(arr[idx].left != NONE) inorder(arr[idx].left);
        bw.write(idx + 'A');
        if(arr[idx].right != NONE) inorder(arr[idx].right);
    }
    public static void postorder(int idx) throws IOException {
        if(arr[idx].left != NONE) postorder(arr[idx].left);
        if(arr[idx].right != NONE) postorder(arr[idx].right);
        bw.write(idx + 'A');
    }
}

class Node {
    int left; // 왼쪽 자식의 인덱스
    int right; // 오른쪽 자식의 인덱스

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

 

문제 링크

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