[BOJ/JAVA] 1991번: 트리 순회

1991번: 트리 순회

문제 이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 프로그램을 작성하시오. 예를 들어 위와 같은 이진 트리가 입력되면, 전위 순회한 결과 : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 자식) 중위 순회한 결과 : DBAECFG // (왼쪽 자식) (루트) (오른쪽 자식) 후위 순회한 결과 : DBEGFCA // (왼쪽 자식) (오른쪽 자식) (루트) 가 된다.

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

키워드

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

---

구현

• Node
  • 현재 값
  • 왼쪽 자식의 값
  • 오른쪽 자식의 값

• alphaIntegerConvert
  • 단일 문자를 A=0, B=1 처럼 정수형으로 변환한다.

• preOrder :: 전위 순회
  • 현재 노드를 탐색한다.
  • 왼쪽 자식을 탐색한다.
  • 오른쪽 자식을 탐색한다.

• inOrder :: 중위순회
  • 왼쪽 자식을 탐색한다.
  • 현재 노드를 탐색한다.
  • 오른쪽 자식을 탐색한다.

• postOrder :: 후위순회
  • 왼쪽 자식을 탐색한다.
  • 오른쪽 자식을 탐색한다.
  • 현재 노드를 탐색한다.

---

코드

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

public class java_1991 {
    static int N;
    static Node tree[];

    static class Node {
        char me, left, right;

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

    static int alphaIntegerConvert(char alpha) {
        return alpha - 'A';
    }


    static void preOrder(char alpha) {
        if (alpha == '.') {
            return;
        }

        int index = alphaIntegerConvert(alpha);

        System.out.print(alpha);
        preOrder(tree[index].left);
        preOrder(tree[index].right);
    }

    static void inOrder(char alpha) {
        if (alpha == '.') {
            return;
        }

        int index = alphaIntegerConvert(alpha);

        inOrder(tree[index].left);
        System.out.print(alpha);
        inOrder(tree[index].right);
    }

    static void postOrder(char alpha) {
        if (alpha == '.') {
            return;
        }

        int index = alphaIntegerConvert(alpha);

        postOrder(tree[index].left);
        postOrder(tree[index].right);
        System.out.print(alpha);
    }

    static void solution() {
        preOrder('A');
        System.out.println();
        inOrder('A');
        System.out.println();
        postOrder('A');
        System.out.println();
    }

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

        tree = new Node[26];

        N = Integer.parseInt(br.readLine());

        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            char me = st.nextToken().charAt(0);
            char left = st.nextToken().charAt(0);
            char right = st.nextToken().charAt(0);

            Node node = new Node(me, left, right);
            int index = alphaIntegerConvert(me);
            tree[index] = node;
        }

        solution();

        br.close();
    }
}

---

Uploaded by N2T