[트리] 백준 트리 순회, 트리의 부모 찾기

트리 순회(1991)

https://www.acmicpc.net/problem/1991

1991번: 트리 순회

HashMap<String, ArrayList<String>> 구조로 데이터를 변환한 후,

차례로 전위, 중위, 후위 순회를 수행한 후 결과 StringBuffer를 출력했다.

전위, 중위, 후위의 차이는 해당 문자가 왼쪽 자식을 찾는 모든 과정 이전에 출력될 경우 전위,

왼쪽 자식을 찾는 모든 과정 이후 오른쪽 자식을 찾는 과정 이전에 출력될 경우 중위,

왼쪽 자식을 모두 찾고, 오른쪽 자식도 모두 찾은 이후 출력될 경우 후위라고 이해했다.

 

public class Main {
    static int N;
    static Map<String, List<String>> list;
    static StringBuffer sb;
    private static void preOrder(String str) {
        if(".".equals(str)) return;
        
        sb.append(str);
        preOrder(list.get(str).get(0));
        preOrder(list.get(str).get(1));
    }
    
    private static void inOrder(String str) {
        if(".".equals(str)) return;
        
        inOrder(list.get(str).get(0));
        sb.append(str);
        inOrder(list.get(str).get(1));
    }
    
    private static void postOrder(String str) {
        if(".".equals(str)) return;
        
        postOrder(list.get(str).get(0));
        postOrder(list.get(str).get(1));
        sb.append(str);
    }
    
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st ;
        N = Integer.parseInt(br.readLine());
        sb = new StringBuffer();
        list = new HashMap<String, List<String>>();
        for(int i=0; i<N; i++) {
            st = new StringTokenizer(br.readLine());
            String value = st.nextToken();
            List<String> childList = new ArrayList<String>();
            for(int j=0; j<2; j++) {
                childList.add(st.nextToken());
            }
            list.put(value, childList);
        }
        
        preOrder("A");
        sb.append("\n");
        inOrder("A");
        sb.append("\n");
        postOrder("A");
        System.out.println(sb);
    }
}