문제 이해

이진 트리의 전위 순회, 중위 순회, 후위 순회한 결과를 출력하는 문제이다.

---

문제 이해

전위 순회 : 루트 ⇒ 왼쪽 자식 ⇒ 오른쪽 자식
중위 순회 : 왼쪽 자식 ⇒ 루트 ⇒ 오른쪽 자식
후위 순회 : 왼쪽 자식 ⇒ 루트 ⇒ 오른쪽 자식

위 3개를 보면, 결국 Root를 언제 출력하느냐의 문제일뿐 세 알고리즘 모두 비슷한 구현법을 사용한다는 것을 알 수 있다.

---

코드

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

class Node{
	char value;
	Node left; // 왼쪽 자식
	Node right; // 오른쪽 자식
	
	Node(char value){
		this.value = value;
		this.left = null;
		this.right = null;
	}
}

public class Main {
	static StringBuilder sb = new StringBuilder();
	static int N;
	static Node[] nodes;
	
	static void preorder(Node n) { 
    // 전위 순회 : 루트 (출력) -> 왼쪽 자식 -> 오른쪽 자식
		sb.append(n.value);
		if(n.left!=null) preorder(n.left);
		if(n.right!=null) preorder(n.right);
	}
	
	static void inorder(Node n) { 
    // 중위 순회 : 왼쪽 자식 -> 루트 (출력) -> 오른쪽 자식
		if(n.left!=null) inorder(n.left);
		sb.append(n.value);
		if(n.right!=null) inorder(n.right);
	}
	
	static void postorder(Node n) { 
    // 후위 순회 : 왼쪽 자식 -> 오른쪽 자식 -> 루트 (출력)
		if(n.left!=null) postorder(n.left);
		if(n.right!=null) postorder(n.right);
		sb.append(n.value);
	}
	
	public static void main(String[] args) {
		FastReader sc = new FastReader();
		
		N = sc.nextInt();
		nodes = new Node[N];
		
		for(int i =0;i<N;i++) {
			char alpha = (char) ('A'+i);
			nodes[i] = new Node(alpha);
		}
		
		for(int i =0;i<N;i++) {
			String tmp = sc.nextLine();
			
			String[] tmp2 = tmp.split(" ");
			char root = tmp2[0].charAt(0);
			char left = tmp2[1].charAt(0);
			char right = tmp2[2].charAt(0);
			
			if(left!='.') nodes[root-'A'].left = nodes[left-'A'];
			if(right!='.') nodes[root-'A'].right = nodes[right-'A'];
		}
		preorder(nodes[0]);
		sb.append("\n");
		
		inorder(nodes[0]);
		sb.append("\n");
		
		postorder(nodes[0]);
		
		System.out.println(sb);
	}
	
	static class FastReader // 빠른 입력을 위한 클래스
}

---

결과