[BOJ/] 백준 1991 - 트리 순회 (Java)

1991 - 트리 순회

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

 

문제

이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)
전위 순회한 결과 : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 자식)
중위 순회한 결과 : DBAECFG // (왼쪽 자식) (루트) (오른쪽 자식)
후위 순회한 결과 : DBEGFCA // (왼쪽 자식) (오른쪽 자식) (루트)

입력
첫째 줄: 이진 트리의 노드의 개수 N (1 <= N <= 26)
둘째 줄부터 N개의 줄: 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어짐
노드의 이름은 A부터 차례대로 알파벳 대문자로 매겨지며, 항상 A가 루트 노드/ 자식 노드 X -> .으로 표현
출력
전위 순회, 중위 순회, 후위 순회 
각 줄에 N개의 알파벳 공백 X 출력

---

풀이

트리 노드

• `char val`: 노드에 저장된 값 
  • ex. 'A', 'B', ...
• `TreeNode lt, rt`: 왼쪽, 오른쪽 자식 노드 가리키는 포인터

class TreeNode {
    char val;
    TreeNode lt, rt;

    public TreeNode(char val) {
        this.val = val;
        this.lt = null;
        this.rt = null;
    }
}

 

전위 순회

root -> L -> R

public static void preOrder(TreeNode root) {
    if (root == null) return;
    pre.append(root.val);
    preOrder(root.lt);
    preOrder(root.rt);
}

 

중위 순회

L -> root -> R

public static void inOrder(TreeNode root) {
    if (root == null) return;
    inOrder(root.lt);
    in.append(root.val);
    inOrder(root.rt);
}

 

후위 순회

L -> R -> root

public static void postOrder(TreeNode root) {
    if (root == null) return;
    postOrder(root.lt);
    postOrder(root.rt);
    post.append(root.val);
}

---

코드

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

// 트리 순회
class TreeNode {
    char val;
    TreeNode lt, rt;

    public TreeNode(char val) {
        this.val = val;
        this.lt = null;
        this.rt = null;
    }
}

public class boj_1991 {
    static TreeNode[] tree = new TreeNode[26];
    static StringBuilder pre = new StringBuilder();
    static StringBuilder in = new StringBuilder();
    static StringBuilder post = new StringBuilder();

    public static void preOrder(TreeNode root) {
        if (root == null) return;
        pre.append(root.val);
        preOrder(root.lt);
        preOrder(root.rt);
    }

    public static void inOrder(TreeNode root) {
        if (root == null) return;
        inOrder(root.lt);
        in.append(root.val);
        inOrder(root.rt);
    }

    public static void postOrder(TreeNode root) {
        if (root == null) return;
        postOrder(root.lt);
        postOrder(root.rt);
        post.append(root.val);
    }

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

        int N = Integer.parseInt(br.readLine());
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            char root = st.nextToken().charAt(0);
            char lt = st.nextToken().charAt(0);
            char rt = st.nextToken().charAt(0);

            if (tree[root - 'A'] == null) {
                tree[root - 'A'] = new TreeNode(root);
            }
            TreeNode cur = tree[root - 'A'];

            if (lt != '.') {
                tree[lt - 'A'] = new TreeNode(lt);
                cur.lt = tree[lt - 'A'];
            }

            if (rt != '.') {
                tree[rt - 'A'] = new TreeNode(rt);
                cur.rt = tree[rt - 'A'];
            }
        }

        TreeNode rootNode = tree[0];
        preOrder(rootNode);
        inOrder(rootNode);
        postOrder(rootNode);

        System.out.println(pre);
        System.out.println(in);
        System.out.println(post);
    }
}