[SWEA] 1231. 중위순회 (Java)

문제

SW Expert Academy

 

풀이

0. 문제 해석

이진트리를 생성하여 중위순회 하는 문제이다.

 

트리를 생성하는 방법은 여러가지가 존재하는데

 

1. 배열로 구현하는 방법

2. 클래스로 연결 리스트로 구현하는 방법

 

등이 있다.

 

이 문제에선 각각 왼쪽 자식의 인덱스가 i * 2, 오른쪽 자식의 인덱스가 i * 2 + 1 인 순차적인 구조이므로

배열로 구현하는 것이 훨씬 간편하다.

 

하지만 이번엔 2번 방법을 사용하여 구현해보려고 한다.

 

1. 트리 클래스 메소드 구현

자신의 인덱스, 데이터와 양쪽 자식을 저장할 노드(정점) 클래스를 만들어준다.

 

이제 트리에 노드를 추가하는 add 메소드를 구현해주는데

최초 생성 (root) 입력 시 그 노드를 root로 하도록 하고 입력받은 좌우 자식을 새로운 노드를 생성하여 넣어준다.

 

이제 두번째 입력 부터는 search 메소드를 구현하여 루트부터 출발하여 노드 좌우에 내가 삽입하려는 노드가 존재하면 그 노드에 데이터 값을 넣어준 후, 좌우 자식을 새로운 노드를 생성하여 넣어준다.

 

이와 같은 형태로 연결리스트 방식의 트리가 구현된다.

 

2. 트리 생성

양쪽 자식이 있는 노드, 한쪽 자식만 있는 노드, 자식 없는 노드를 입력받았을 때에 대한 처리를 해주고

트리에 add 메소드로 추가해준다.

 

3. 중위 순회

재귀로 중위순회를 하여 출력한다.

 

4. 전체 코드

// [SWEA] 1231. 중위순회 (Java)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

// 트리 노드
class Node{
	int index;
	char data;
	Node leftNode;
	Node rightNode;
	
	public Node(int index) {
		this.index = index;
		this.data = ' ';
		leftNode = null;
		rightNode = null;
	}
}

// 트리 클래스
class Tree{
	Node root = null;
	
	public void add(int index, char data, int leftIndex, int rightIndex) {
		// 트리 최초 생성 시
		if(root == null) {
			root = new Node(index);
			root.data = data;
			if(leftIndex != 0) root.leftNode = new Node(leftIndex);
			if(rightIndex != 0) root.rightNode = new Node(rightIndex);
		}
		else {
			search(root,index,data,leftIndex,rightIndex);
		}
	}
	
	// 이미 존재하는 노드에 연결
	public void search(Node root, int index, char data, int leftIndex, int rightIndex) {	
		// 찾았을 때 좌우 연결
		if(root.index == index) {
			root.data = data;
			if(leftIndex != 0) root.leftNode = new Node(leftIndex);
			if(rightIndex != 0) root.rightNode = new Node(rightIndex);
		}
		
		// 못 찾으면 좌우 탐색
		else {
			if(root.leftNode != null) search(root.leftNode,index,data,leftIndex,rightIndex);
			if(root.rightNode != null) search(root.rightNode,index,data,leftIndex,rightIndex);
		}
	}
	
	// 중위 순회 (왼쪽 자식, 루트, 오른쪽 자식)
	public void inOrder(Node root) {
		if(root.leftNode != null) inOrder(root.leftNode);
		System.out.print(root.data);
		if(root.rightNode != null) inOrder(root.rightNode);
	}
}

public class Solution {
	static int n; // 정점의 총 수
	static Tree tree; // 트리
	
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    	for(int t = 1; t <= 10; t++) {
    		n = Integer.parseInt(br.readLine());
    		tree = new Tree();
		
    		for(int i = 1; i <= n; i++) {
    			StringTokenizer st = new StringTokenizer(br.readLine());
    			st.nextToken();
    			char data = st.nextToken().charAt(0);
    			int leftIndex = 0;
    			int rightIndex = 0;
    			
    			if (st.countTokens() == 2) {
    				leftIndex = Integer.parseInt(st.nextToken());
    				rightIndex = Integer.parseInt(st.nextToken());
    			}
    			else if (st.countTokens() == 1){
    				leftIndex = Integer.parseInt(st.nextToken());
    			}
    			
    			tree.add(i, data, leftIndex, rightIndex);
    		}
    		
    		System.out.print("#" + t + " ");
    		tree.inOrder(tree.root);
    		System.out.println();
    	}
    }
}