[알고리즘] 백준 4256 - 트리(순회)

분류 : 트리

1. 문제

https://www.acmicpc.net/problem/4256
이진 트리는 매우 중요한 기본 자료 구조이다. 아래 그림은 루트 노드가 유일한 이진 트리이다. 모든 노드는 최대 2개의 자식 노드를 가질 수 있으며, 왼쪽 자식이 순서가 먼저이다. 노드 n개로 이루어진 이진 트리를 BT라고 하자. BT의 노드는 1부터 n까지 유일한 번호가 매겨져 있다.

아래 그림에 나와있는 BT의 루트는 3번 노드이다. 1번 노드는 오른쪽 자식만 가지고 있고, 4와 7은 왼쪽 자식만 가지고 있다. 3과 6은 왼쪽과 오른쪽 자식을 모두 가지고 있다. 나머지 노드는 모두 자식이 없으며, 이러한 노드는 리프 노드라고 부른다.

BT의 모든 노드를 순회하는 방법은 전위 순회(preorder), 중위 순회(inorder), 후위 순회(postorder)로 총 세 가지가 있다. 이 세 방법은 아래에 C 스타일의 의사 코드로 나와 있다. BT의 노드 v에 대해서, v.left는 왼쪽 자식, v.right는 오른쪽 자식을 나타낸다. v가 왼쪽 자식이 없으면 v.left는 ∅와 같고, 오른쪽 자식이 없으면 v.right는 ∅와 같다.

BT를 전위 순회, 중위 순회한 결과가 주어진다. 즉, 위의 함수 중 preorder(root node of BT)와 inorder(root node of BT)를 호출해서 만든 리스트가 주어진다. 두 순회한 결과를 가지고 다시 BT를 만들 수 있다. BT의 전위, 중위 순회한 결과가 주어졌을 때, 후위 순회했을 때의 결과를 구하는 프로그램을 작성하시오.

예를 들어, 위의 그림을 전위 순회하면 3,6,5,4,8,7,1,2, 중위 순회하면 5,6,8,4,3,1,2,7이 된다. 이를 이용해 후위 순회하면 5,8,4,6,2,1,7,3이 된다.

2. 입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 노드의 개수 n이 주어진다. (1 ≤ n ≤ 1,000) BT의 모든 노드에는 1부터 n까지 서로 다른 번호가 매겨져 있다. 다음 줄에는 BT를 전위 순회한 결과, 그 다음 줄에는 중위 순회한 결과가 주어진다. 항상 두 순회 결과로 유일한 이진 트리가 만들어지는 경우만 입력으로 주어진다.

3. 풀이

원래 트리 순회할 때는 기본 트리 배열을 기준으로 순회한다.

기본 트리 배열(인덱스)
i : 부모 노드 위치
(i+1)2 -1 : 왼쪽 자식 노드 위치
(i+1)2 : 오른쪽 자식 노드 위치

문제에서는 기본 트리 배열이 주어지지 않지만, postorder를 기본 트리 배열이 아닌 전위 순회와 중위 순회 배열에서 인덱스를 바로 찾아 적용해서 풀 수 있다.

전위순회의 0번째 원소가 트리의 루트 노드이다.
현재 서브 트리의 루트 노드(부모 노드)를 중위 순회에서 찾으면

• 해당 노드 기준으로 왼쪽이 왼쪽 자식 노드
• 해당 노드 기준으로 오른쪽이 오른쪽 자식 노드

예시)

전위 순회 : 3 /6 5 4 8 /7 1 2
중위 순회 : 5 6 8 4 /3/ 1 2 7
3이 루트 노드, 5684가 왼쪽 서브트리, 127이 오른쪽 서브트리

1) 왼쪽 서브트리 찾기
2) 오른쪽 서브트리 찾기
3) 부모노드(자기자신) 출력

이를 분할정복처럼 반복해주면 후위 순회에서 원하는 왼쪽 노드 - 오른쪽 노드 - 부모 노드 순으로 출력할 수 있다.

재귀함수 만들 때

postorder(서브트리 시작위치(중위순회에서), 서브트리 끝위치(=이전 루트노드 위치), 전위순회에서 다음 루트노드 위치)
왼쪽 : 다음 루트노드 위치는 현재 루트노드 위치(전위순회에서)+1
오른쪽 : 다음 루트노드 위치는 현재 루트노드 위치(전위순회에서) + (중위순회에서 다음 루트노드 위치 - 중위순회 오른쪽 트리 시작 위치) + 1

> (중위순회에서 다음 루트노드 위치 - 중위순회 오른쪽 트리 시작 위치) = 오른쪽 트리 기준 루트노드의 왼쪽 자식 노드 숫자

4. 코드

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

public class binaryTree {

    static int[] pre_tree;
    static int[] in_tree;

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

        //tc 개수
        int tc = Integer.parseInt(bf.readLine());

        for(int i=0;i<tc;i++){

            //노드 개수
            int n = Integer.parseInt(bf.readLine());

            pre_tree = new int[n];
            in_tree = new int[n];

            StringTokenizer st = new StringTokenizer(bf.readLine()," ");
            for(int j=0;j<n;j++) {
                pre_tree[j] = Integer.parseInt(st.nextToken());
            }
            st = new StringTokenizer(bf.readLine()," ");
            for(int j=0;j<n;j++) {
                in_tree[j] = Integer.parseInt(st.nextToken());
            }

            postorder(0,n,0);
            System.out.println();

        }


    }

    public static void postorder(int start, int end, int parent){
        for(int i = start; i<end;i++){
            if(in_tree[i] == pre_tree[parent]){
            	//왼쪽 서브트리
                postorder(start, i, parent+1);
                //오른쪽 서브트리
                postorder(i+1, end, parent+i-start+1);
                System.out.print(pre_tree[parent] + " ");
            }
        }
    }


}