[SWEA] 1231 - 중위 순회

트리가 완전 이진트리 형식으로 주어지기 때문에, 배열로 트리를 만들어서 구현하였다.

입력값 중 index와 해당 알파벳 말고는 사용하지 않아도 구현이 가능하다. (index도 사실 순서대로 들어오기 때문에 필요하지 않다)

배열의 index를 1부터 사용하여 i가 인덱스인 노드의 자식 노드는 각각 2*i, 2*i+1의 인덱스를 가진다.

이를 활용하면 배열을 이진트리처럼 활용하여 전위, 중위, 후위 순회가 가능하다.

			String[] tree = new String[N + 1];

			for (int i = 0; i < N; i++) {
				StringTokenizer st = new StringTokenizer(br.readLine());
				int index = Integer.parseInt(st.nextToken());
				String alphabet = st.nextToken();
				tree[index] = alphabet;
			}

index와 알파벳만 사용하기 위해 StringTokenizer를 사용하였다. (리프 노드는 자식 노드가 입력되지 않기 때문에 스캐너로 처리하기 까다로움)

tree배열은 1부터 사용할 것이기 때문에 길이를 N+1로 선언하였고 tree의 각 index에 alphabet을 담는다.

 

중위 순회

static void inOrder(String[] tree, int i) {
		if (i < tree.length) {
			inOrder(tree, 2 * i);
			sb.append(tree[i]);
			inOrder(tree, 2 * i + 1);
		}
	}

완전 이진트리이기 때문에 트리는 모두 꽉 차있어서 해당 노드가 리프노드인지의 여부는 i가 배열의 크기를 벗어났는지 확인하면 된다.

그래서 i가 tree의 길이보다 작다면 순회를 계속한다. 중위 순회는 왼쪽 자식노드 - 부모노드 - 오른쪽 자식노드 순으로 순회하기 때문에 위 코드와 같이 재귀적으로 순회하면 된다.

---

전체 코드

package d4;

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

public class SWEA_1231_중위순회 {
	static StringBuilder sb = new StringBuilder();

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = 10;
		for (int t = 1; t <= 10; t++) {
			int N = Integer.parseInt(br.readLine());
			String[] tree = new String[N + 1];

			for (int i = 0; i < N; i++) {
				StringTokenizer st = new StringTokenizer(br.readLine());
				int index = Integer.parseInt(st.nextToken());
				String alphabet = st.nextToken();
				tree[index] = alphabet;
			}
			sb.append("#" + t + " ");
			inOrder(tree, 1);
			System.out.println(sb.toString());
			sb.setLength(0);
		}

	}// main

	static void inOrder(String[] tree, int i) {
		if (i < tree.length) {
			inOrder(tree, 2 * i);
			sb.append(tree[i]);
			inOrder(tree, 2 * i + 1);
		}
	}
}