[백준 1991] 트리 순회(JAVA)

백준 1991번 문제 - 트리 순회

1991번: 트리 순회

---

문제 분석 

 

 

• 이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 프로그램 만들기
  • 전위 순회: (루트) (왼쪽 자식) (오른쪽 자식)
  • 중위 순회 : (왼쪽 자식) (루트) (오른쪽 자식)
  • 후위 순회 : (왼쪽 자식) (오른쪽 자식) (루트)

---

해결 포인트

 

• 재귀 함수 사용
• 트리 노드 클래스 구현
• 전위, 중위, 후위 하고싶은 순회에 따라 DFS 호출 다르게
  • 전위 : 현재 문자 출력 + 함수 실행(left) + 함수 실행(right)
  • 중위 :  함수 실행(left) + 현재 문자 출력 + 함수 실행(right)
  • 후위 : 함수 실행(left) + 함수 실행(right) + 현재 문자 출력

---

코드

 

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

        Node [] nodes = new Node[N];
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            char a = st.nextToken().charAt(0);
            char b = st.nextToken().charAt(0);
            char c = st.nextToken().charAt(0);

            int index = a - 'A';
            nodes[index] = new Node(a,b,c);
        }

        bw.write(getPreorder(nodes, 0) + "\n");
        bw.write(getInorder(nodes, 0) + "\n");
        bw.write(getPostorder(nodes, 0) + "\n");

        bw.flush();
        bw.close();
    }
    public static class Node {
        int left = -1;
        int right = -1;
        char curr;
        public Node(char curr, char left, char right) {
            this.curr = curr;
            if(left != '.')
                this.left = left - 'A';
            if(right != '.')
                this.right = right - 'A';
        }
    }

    public static String getPreorder(Node [] nodes, int index) {
        StringBuilder result = new StringBuilder();

        result.append(nodes[index].curr);
        if(nodes[index].left != -1) {
            result.append(getPreorder(nodes, nodes[index].left));
        }

        if(nodes[index].right != -1) {
            result.append(getPreorder(nodes, nodes[index].right));
        }

        return result.toString();
    }

    public static String getInorder(Node [] nodes, int index) {
        StringBuilder result = new StringBuilder();

        if(nodes[index].left != -1) {
            result.append(getInorder(nodes, nodes[index].left));
        }

        result.append(nodes[index].curr);

        if(nodes[index].right != -1) {
            result.append(getInorder(nodes, nodes[index].right));
        }

        return result.toString();
    }

    public static String getPostorder(Node [] nodes, int index) {
        StringBuilder result = new StringBuilder();

        if(nodes[index].left != -1) {
            result.append(getPostorder(nodes, nodes[index].left));
        }

        if(nodes[index].right != -1) {
            result.append(getPostorder(nodes, nodes[index].right));
        }

        result.append(nodes[index].curr);

        return result.toString();
    }
}