백준 1991 - 트리 순회

문제 풀이

 

각 노드의 root 값을 인덱스로 삼아 ArrayList에 저장하고 읽고 쓰는 방식을 이용하여 풀었습니다.

 

전위 순회 ( PreOrder)는 root, left, right 순,

중위 순회 ( InOrder )는 left, root, right 순

후위 순회 (PostOrder )는 left, right, root 순으로 탐색을 하는 방법입니다. 

 

 

이를 코드로 구현하면

 

전휘 순회 ( PreOrder ) : 출력이 1, left 탐색 2, right 탐색 3

    // root - left - right
    public static void preOrder(char node) throws IOException {
        if (node == '.') return;
 
        bw.write(node);
        preOrder(tree.get(node - 'A').left);
        preOrder(tree.get(node - 'A').right);
    }

 

중위 순회 ( InOrder ) : left 탐색 1, 출력 2, right 탐색 3

// left - root - right
    public static void inOrder(char node) throws IOException {
        if (node == '.') return;
 
        inOrder(tree.get(node - 'A').left);
        bw.write(node);
        inOrder(tree.get(node - 'A').right);
    }

 

후위 순회 ( PostOrder ) : left 탐색 1, right 탐색 2 , 출력 3

// left - right - root
    public static void postOrder(char node) throws IOException {
        if (node == '.') return;
 
        postOrder(tree.get(node - 'A').left);
        postOrder(tree.get(node - 'A').right);
        bw.write(node);
    }

 

전체 코드

 

import java.io.*;
import java.util.*;
 
public class Main {
    static int N;
    static ArrayList<Node> tree;
    static BufferedWriter bw;
    public static void main(String [] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        N = Integer.parseInt(br.readLine());
        tree = new ArrayList<>(N+1);
 
        for (int i = 0 ; i <= N ; i++) {
            tree.add(new Node('A','A'));
        }
 
        char rt ='A', l , r;
        StringTokenizer st;
 
        for (int i = 0 ; i < N ; i++) {
            st = new StringTokenizer(br.readLine());
            rt = st.nextToken().charAt(0);
            l = st.nextToken().charAt(0);
            r = st.nextToken().charAt(0);
            Node node = new Node(l, r);
            tree.set(rt - 'A', node);
        }
 
        preOrder('A');
        bw.write("\n");
        bw.flush();
        inOrder('A');
        bw.write("\n");
        bw.flush();
        postOrder('A');
        bw.write("\n");
        bw.flush();
    }
 
    // root - left - right
    public static void preOrder(char node) throws IOException {
        if (node == '.') return;
 
        bw.write(node);
        preOrder(tree.get(node - 'A').left);
        preOrder(tree.get(node - 'A').right);
    }
 
    // left - root - right
    public static void inOrder(char node) throws IOException {
        if (node == '.') return;
 
        inOrder(tree.get(node - 'A').left);
        bw.write(node);
        inOrder(tree.get(node - 'A').right);
    }
 
    // left - right - root
    public static void postOrder(char node) throws IOException {
        if (node == '.') return;
 
        postOrder(tree.get(node - 'A').left);
        postOrder(tree.get(node - 'A').right);
        bw.write(node);
    }
}
 
class Node {
    public char left;
    public char right;
    public Node( char l, char r) {
        left = l;
        right = r;
    }
}