[백준] 1991번 트리순회 출력문제 코드 : Programming Story

1. 문제

1) 링크

www.acmicpc.net/problem/1991

2) 문제

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

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

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

가 된다.

3) 입력

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

4) 출력

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

더 자세한 문제의 제한을 보기 위해서는 위의 백준 링크에 들어가 보자

2. 트리 자료 구조

이 문제는 트리의 구조와 트리의 순화방법을 알지 못한다면 절대로 풀 수 없는 문제이다.

만약 트리 자료구조를 알지 못하면

https://www.programmingstory.com/2024/02/blog-post_11.html

이전 포스팅을 먼저 보고 오자.

3. 풀이

우선 트리 구조를 구현하기 위해서 Node class를 사용했다. 자바에서는 구조체와 같은 역할을 하는 것이 class이기 때문에 클래스를 하나 더 만들어주었다.

필요한 요소는 왼쪽 자식 노드와 오른쪽 자식 노드이기 때문에

다음과 같이 코드를 작성할 수 있다.


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

그리고 만약 자식 노드가 없다면 해당 노드의 값은 -1로 표시하여 leaf node인지 아닌지를 판단할 수 있어야 한다.

그래서 post-order, in-order, pre-order를 할 때도 -1의 값이 나오면 값을 return 해주면서 끝을 알릴 수 있어야 한다.

여기서 각각의 함수를 static으로 만들고 호출해줄 것인데, 사실 코드는 거의 유사하다. 현재 노드를 출력하는 출력 라인의 순서만 달라지는 것이다.

1] preorder 함수

 static void preorder( int x) {
        if (x == -1) return;
        System.out.print((char)(x+'A'));
        preorder(a[x].left);
        preorder(a[x].right);
    }

preorder 함수는 먼저 현재 노드를 출력해주고, 좌측 자식노드와 우측 자식노드를 차례대로 출력해준다.

노드의 값이 -1이라면 더 이상 자식 노드가 없다는 뜻이므로 return 해준다.

2] inorder 함수

static void inorder(int x) {
        if (x == -1) return;
        inorder(a[x].left);
        System.out.print((char)(x+'A'));
        inorder(a[x].right);
    }

inorder는 좌측 자식 노드를 출력, 현재 노드 출력, 우측 자식 노드를 출력하는 식으로 이루어진다.

노드의 값이 -1이라면 preorder와 마찬가지로 자식 노드가 없다는 뜻이므로 return 해준다.

3] postorder 함수

 static void postorder(int x) {
        if (x == -1) return;
        postorder(a[x].left);
        postorder(a[x].right);
        System.out.print((char)(x+'A'));
    }

postorder는 현재 노드를 가장 마지막에 출력해주는 것이다. 즉, 좌측 자식 노드와 우측 자식 노드 부분을 먼저 다 출력한 다음에 출력해준다. 노드의 값이 -1이라면 preorder와 마찬가지로 자식 노드가 없다는 뜻이므로 return 해준다.

4. 코드

이런식으로 비슷하게 세 가지 함수를 비슷하게 코드 작성해줄 수 있다.

전체 코드를 살펴보면, 다음과 같다.

import java.util.*;
class Node {
    int left, right;
    Node(int left, int right) {
        this.left = left;
        this.right = right;
    }
}
public class Main{
    static Node[] a;
    static void preorder( int x) {
        if (x == -1) return;
        System.out.print((char)(x+'A'));
        preorder(a[x].left);
        preorder(a[x].right);
    }
    static void inorder(int x) {
        if (x == -1) return;
        inorder(a[x].left);
        System.out.print((char)(x+'A'));
        inorder(a[x].right);
    }
    static void postorder(int x) {
        if (x == -1) return;
        postorder(a[x].left);
        postorder(a[x].right);
        System.out.print((char)(x+'A'));
    }
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        a=new Node[26];
        for(int i=0; i<n; i++){
            int current=sc.next().charAt(0)-'A';
            char le=sc.next().charAt(0);
            char ri=sc.next().charAt(0);
            
            int left = -1;
            int right = -1;
            if (le != '.') {
                left = le-'A';
            }
            if (ri != '.') {
                right = ri-'A';
            }
            a[current] = new Node(left, right);
        }
        preorder(0);
        System.out.println();
        inorder(0);
        System.out.println();
        postorder(0);
        System.out.println();
    }
}