[BOJ] 1991: 트리순회 (JAVA)

백준 1991: 트리순회 (실버1)

 

 

풀이

 

트리의 순회를 코드로 구현하는 문제다.

전위순회는 N-L-R / 중위순회는 L-N-R / 후위 순회는 L-R-N 순으로 순회한다.

(L = 왼쪽 자식, N = 뿌리 노드, R = 오른쪽 자식)

 

노드를 저장하는 배열의 순서는 char를 사용해서 -'A'를 해주며 순서를 저장해준다.

 

전체코드

import java.io.*;
import java.util.*;

public class Main{
	static class Node{
		char N;
		Node left;
		Node right;
		Node(char N){
			this.N = N;
			this.left = left;
			this.right = right;
		}
	}
	static Node[] tree;
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		tree = new Node[n+1];
		
		for(int i=0; i<n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			
			char nodeValue = st.nextToken().charAt(0);
			char leftValue = st.nextToken().charAt(0);
			char rightValue = st.nextToken().charAt(0);
			
			if(tree[nodeValue - 'A'] == null) {
				tree[nodeValue - 'A'] = new Node(nodeValue);
			}
			if(leftValue != '.') {
				tree[leftValue - 'A'] = new Node(leftValue);
				tree[nodeValue - 'A'].left = tree[leftValue - 'A'];
			}
			if(rightValue != '.') {
				tree[rightValue - 'A'] = new Node(rightValue);
				tree[nodeValue - 'A'].right = tree[rightValue - 'A'];
			}
		}
		
		preOrder(tree[0]);
		System.out.println();
		inOrder(tree[0]);
		System.out.println();
		postOrder(tree[0]);
	}
	
	static void preOrder(Node node) {
		if(node == null) return;
		System.out.print(node.N);
		preOrder(node.left);
		preOrder(node.right);
	}
	
	static void inOrder(Node node) {
		if(node == null) return;
		inOrder(node.left);
		System.out.print(node.N);
		inOrder(node.right);
	}
	
	static void postOrder(Node node) {
		if(node == null) return;
		postOrder(node.left);
		postOrder(node.right);
		System.out.print(node.N);
	}
	
}