백준 1991번 트리순회 S1 - 전위 중위 후위 순회

 

이진트리 입력이 주어지고, 해당 트리를

전위 중위 후위한 결과를 출력하는 문제이다.

입력에 . 은 자식이 없다는 의미로 받아주면 된다.

 

트리를 순회할때는 큰 삼각형을 작은 삼각형으로 쪼개서 순회한다고 생각했다.

따라서 재귀함수로 작성하는게 문제의 포인트이다.

 

Node 클래스로 왼쪽과 오른쪽 자식을 관리해 주었고,

'.' 입력이 주어질때는 자식에 Null을 주는 방식으로 처리를 했다.

 

전위 순회의 경우 루트 먼저, 이후 왼 > 오 자식을 순회하고.

중위의 경우 왼쪽 아래까지 쭉 내려갔다가 더이상 자식이 없으면 루트, 오른쪽 자식을 찾는 방식이다.

마지막으로 후위는 왼쪽 아래 탐색 후 오른쪽 아래 탐색. 이후 없다면 부모 노트 체크. 이다.

 

결론적으로 

전위는 출력하고 왼쪽 오른쪽 재귀함수를 호출.

중위는 왼쪽 재귀를 호출 후 출력. 이후 오른쪽 재귀 호출.

후위는 왼쪽 오른쪽 재귀 호출 후 출력이 되겠다.

 

정리가 잘되어 있어서 가져왔다 ^<^.//

 

import java.io.*;
import java.util.*;
 
class Node {
    String value;
    Node left;
    Node right;
 
    Node(String value, Node left, Node right) {
        this.value = value;
        this.left = left;
        this.right = right;
    }
}
 
public class Main { // Boj_1991_트리 순회
 
 
    static int N;
    // 루트는 A로 고정
    static Node head = new Node("A", null, null);
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        StringTokenizer st;
        for(int tc = 0; tc<N; tc++) {
                st = new StringTokenizer(br.readLine());
                String now = st.nextToken();
                String left = st.nextToken();
                String right = st.nextToken();
                setNode(head, now, left, right);
        }
        preOrder(head);
        System.out.println();
        inOrder(head);
        System.out.println();
        postOrder(head);
    }
 
    public static void setNode(Node head, String root, String left, String right) {
        if (head.value.equals(root)) { // 처음 나온 알파뱃이면 새로 만들기.
            head.left = (left.equals(".")) ? null : new Node(left, null, null);
            head.right = (right.equals(".")) ? null : new Node(right, null, null);
        } else {
            if (head.left != null) {
                setNode(head.left, root, left, right);
            }
            if (head.right != null) {
                setNode(head.right, root, left, right);
            }
        }
    }
 
    public static void preOrder(Node node) { // 전위
        if (node == null)
            return;
        System.out.print(node.value);
        preOrder(node.left);
        preOrder(node.right);
    }
    public static void inOrder(Node node) { // 중위
        if (node == null)
            return;
        inOrder(node.left);
        System.out.print(node.value);
        inOrder(node.right);
    }
    public static void postOrder(Node node) { // 
        if (node == null)
            return;
        postOrder(node.left);
        postOrder(node.right);
        System.out.print(node.value);
    }
}
 

 

 

참고 :: https://www.youtube.com/watch?app=desktop&v=WLvU5EQVZqY