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

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

트리 순회

문제

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

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

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

가 된다.

입력

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

출력

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

예제 입력 1 복사

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

예제 출력 1 복사

ABDCEFG
DBAECFG
DBEGFCA

 

---

풀이

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

public class Main {
    static Node[] tree = new Node[26]; // A-Z (최대 26개)
    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<26; i++){
            tree[i] = new Node((char)('A' + i)); // A-Z 노드 미리 생성
        }

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

            // left, right 노드 비어있지 않다면 parent의 left/right 노드에 저장해주기
            if (left != '.'){
                tree[parent - 'A'].left = tree[left - 'A'];
            }

            if (right != '.'){
                tree[parent - 'A'].right = tree[right - 'A'];
            }
        }

        // 전위순회
        preOrder(tree[0]); // A가 루트노드
        System.out.println();

        // 중위순회
        inOrder(tree[0]);
        System.out.println();

        // 후위순회
        postOrder(tree[0]);
    }

    // 전위순회 VLR
    private static void preOrder(Node node){
        if (node == null) return;
        System.out.print(node.data); // 루트
        preOrder(node.left);
        preOrder(node.right);
    }
    // 중위순회 LVR
    private static void inOrder(Node node){
        if (node == null) return;
        inOrder(node.left);
        System.out.print(node.data);
        inOrder(node.right);
    }
    // 후위순회 LRV
    private static void postOrder(Node node){
        if (node == null) return;
        postOrder(node.left);
        postOrder(node.right);
        System.out.print(node.data);
    }
}
class Node{
    char data;
    Node left;
    Node right;

    public Node(char data){
        this.data = data;
        this.left = null;
        this.right = null;
    }
}

• 트리, 순회, 문자 파싱(문자 -> 숫자)을 활용한 문제
• 자기자신과 자식노드들을 같이 저장해주기 위해 Node라는 사용자정의 클래스를 선언해준다.
  • data(자기자신)
  • left 왼쪽 자식노드, right 오른쪽 자식노드
  • 자식노드들은 Node 클래스로 저장해준다.
  • 생성자는 자기자신만 저장하되, 자식노드들은 일단 null로 두도록 정의하였다.
• 노드의 최대개수는 26개로 A~Z까지 이다.
• 따라서 먼저 A ~ Z까지 노드를 담고 있는 배열을 미리 만들어준다.
  • A부터 index 0으로 시작한다.
• 입력으로 받은 N번동안 자식노드에 대한 정보를 받아준다.

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

            // left, right 노드 비어있지 않다면 parent의 left/right 노드에 저장해주기
            if (left != '.'){
                tree[parent - 'A'].left = tree[left - 'A'];
            }

            if (right != '.'){
                tree[parent - 'A'].right = tree[right - 'A'];
            }
        }

• left, right가 '.'이 아니라면 자식노드가 있다는 뜻이므로,  parent의 left, right 노드에 등록해준다.
• tree배열에서 A를 0부터 담아줬기 때문에 parent - 'A' 값의 index가 부모index 값이다.
  
  • 'A' - 'A' = 0 → tree[0]
  • 'B' - 'A' = 1 → tree[1]
  • 'C' - 'A' = 2 → tree[2]

전위순회 VLR (preOrder)

• 루트 -> 왼쪽 자식 -> 오른쪽 자식 노드 순으로 순회한다.
• 종료조건 : 파라미터로 받은 node가 Null이라면 함수를 종료시켜준다.
• node.data 출력 -> preOrder(node.left) 재귀호출 -> preOrder(node.right) 재귀호출

중위순회 LVR (inOrder)

• 왼쪽 자식 -> 루트 -> 오른쪽 자식 노드 순으로 순회한다.
• 종료조건 : 파라미터로 받은 node가 Null이라면 함수를 종료시켜준다.
• inOrder(node.left) 재귀호출 -> node.data 출력 -> inOrder(node.right) 재귀호출

후위순회 LRV (postOrder)

• 왼쪽 자식 -> 오른쪽 자식 노드 -> 루트순으로 순회한다.
• 종료조건 : 파라미터로 받은 node가 Null이라면 함수를 종료시켜준다.
• postOrder(node.left) 재귀호출 -> postOrder(node.right) 재귀호출 -> node.data 출력