백준 1991 트리 순회 (Java)

1. 문제 링크

1991번: 트리 순회

 

2. 문제 및 입출력예제

 

3. 문제 풀이

트리의 노드를 나타낼 노드 클래스를 만든다.

여기서 노드 클래스는 자기 알파벳 + 왼쪽 노드 + 오른쪽 노드로 구성되어 있다.

 

입력받기 전에 문제에 따라 알파벳 순으로 배열에 넣어둔다. (순차적으로 넣기 위해 char를 사용했다.)

입력을 받으면서 왼쪽 자식과 오른쪽 자식을 노드 클래스의 left와 right에 넣는다.

 

재귀를 이용해 각각 전위, 중위, 후위 순회를 하면 끝이다.

 

4. 코드

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

class Node{
	char me;
	Node left, right;
	public Node(char me) {
		this.me = me;
	}
	@Override
	public String toString() {
		return me+" ";
	}
}

public class Main {
	private static int N;
	private static StringBuilder sb;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 
		sb = new StringBuilder();
		N = Integer.parseInt(br.readLine());
		Node[] tree = new Node[N];
		char temp = 'A'; 
		for(int i=0;i<N;i++) {
			tree[i] = new Node(temp++);
		}
        
		for(int i=0;i<N;i++) {
			String split = br.readLine();
			char me = split.charAt(0);
			char left = split.charAt(2);
			char right = split.charAt(4);
			if(left != '.') {
				tree[me-'A'].left = tree[left-'A'];
			}
			if(right != '.') {
				tree[me-'A'].right = tree[right-'A'];
			}
		}
		preorder(tree[0]);
		sb.append("\n");
		inorder(tree[0]);
		sb.append("\n");
		postorder(tree[0]);
		System.out.println(sb);
	}
	
	private static void preorder(Node node) {
		sb.append(node.me);
		if(node.left != null) {
			preorder(node.left);
		}
		if(node.right != null) {
			preorder(node.right);
		}
	}
	private static void inorder(Node node) {
		if(node.left != null) {
			inorder(node.left);
		}
		sb.append(node.me);
		if(node.right != null) {
			inorder(node.right);
		}
	}
	private static void postorder(Node node) {
		if(node.left != null) {
			postorder(node.left);
		}
		if(node.right != null) {
			postorder(node.right);
		}
		sb.append(node.me);
	}
}