SWE 1231(중위순회)

작성일

SWE 1231

이 문제는 완전 이진 트리 형식으로 주어진다고 조건에 명시가 되어 있다.

완전 이진트리는 배열로 구현이 가능하며, 배열 안에서 인덱스로 특정 노드의 부모, 자식 위치를 구할 수 있다.

아래와 같다.

노드 i의 부모 : (i-1)/2
노드 i의 왼쪽 자식 : (2*i)+1
노드 i의 오른쪽 자식 : (2*i) +2

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

public class Solution {
	
	static int T = 2;
	static int n;
	static char[] map;
	static StringBuilder sb = new StringBuilder();
	
	
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int t = 1;
		while(T-- > 0) {
			n = Integer.parseInt(br.readLine()); // 정점의 총 수 저장 
			map = new char[n]; // 정점의 수 만큼 char형 배열 생성 .
			
			for(int i = 0 ;i < n; i++) { 
				StringTokenizer st = new StringTokenizer(br.readLine());
				st.nextToken(); // 1 W 2 3일 때, 필요한 정보는 W부터. 
				map[i] = st.nextToken().charAt(0); //string 을 char로 변환 
				while(st.hasMoreTokens()) // st에 더 많은 토큰이 있다면
					st.nextToken();  // 2와 3 역시 배열에 들어가는 정보가 아니므로 넘긴다. 
			}
			sb.append("#"+(t++)+" ");
			inOrder(0);
			System.out.println(sb.toString());
			sb.setLength(0); //초기화 ?
			
			// sb를 초기화 시키는 방법은 대개 두가지.
			//null로 객체를 없애버리고 다시생성하기. 혹은
			// setLength(0)이다.
			}
		}
	static void inOrder(int node) {
		if((2*node)+1 < n) inOrder((2*node)+1);
		sb.append(map[node]);
		if((2*node)+2< n) inOrder((2*node)+2);
	}
}

참고자료

https://jaejin89.tistory.com/113

sb 초기화

https://blog.outsider.ne.kr/265

0%