[S/W 문제해결 기본] 중위순회 (D4)

문제 링크

• 완전이진트리를 순회
• 순회하는 방법에는 전위순회, 중위순회, 후위순회가 있다
  • 모두 왼쪽 오른쪽을 순서로 돌고, 본인을 앞에 체크할건지, 중간에 할건지 뒤에 할건지만 다르기 때문에 하나의 순회를 구현할 줄 안다면 나머지 둘의 순회도 쉽게 구현할 수 있다
• 해당 문제는 완전이진트리이므로 트리를 굳이 구현하지 않아도 배열을 사용하면 더 빨리, 쉽게 풀 수 있다
• 일차원 배열을 사용했을때,
  • 해당 노드(idx)의 부모 노드는 idx/2
  • 해당 노드의 자식 노드는 왼쪽 자식은 idx*2 오른쪽 자식은 idx*2+1

Solution

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

// [S/W 문제해결 기본] 9일차 - 중위순회
public class Solution {
	static int N;
	static String[] alpha;
	
	public static void inOrder(int idx) {
		if(idx*2 <= N) inOrder(idx*2); // 왼쪽자식 있으면 왼쪽자식 돌기
		System.out.print(alpha[idx]); // 본인
		if(idx*2+1 <= N) inOrder(idx*2+1); // 오른쪽자식 있으면 오른쪽 자식 돌기
	}
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer stk;
		
		for(int t=1; t<=10; t++) {
			N = Integer.parseInt(br.readLine());
			alpha = new String[N+1]; // N까지 있는 배열로 생성
			
			for(int i=0; i<N; i++) {
				stk = new StringTokenizer(br.readLine(), " ");
				alpha[Integer.parseInt(stk.nextToken())] = stk.nextToken(); // 인덱스에 스트링 넣기
				// 나머지 토큰은 그냥 버려
			}
			System.out.printf("#%d ", t);
			inOrder(1);
			System.out.println();
		}
	}
}