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

트리 순회

풀이

인풋으로 한 줄에 노드와 그 노드의 왼쪽, 오른쪽 노드가 주어진다.

간단하게 node를 이용해 구현했다.

우선 인풋으로 들어온 값을 처리하기 위해 node에 현재 노드의 이름과 현재 노드의 자식들의 이름을 저장해둔다.

그리고 저장된 노드들을 하나씩 꺼내면서 노드의 왼쪽과 오른쪽을 맞춰준다.

방법은 다음과 같다.

현재 노드의 왼쪽 자식의 이름과 비교하는 노드의 이름이 같다면 비교하는 노드를 현재 노드의 왼쪽 자식이랑 맞춰주고 비교하는 노드의 부모를 현재 노드로 바꿔준다.
현재 노드의 오른쪽 자식 이름이 비교하는 노드의 이름과 같다면 마찬가지로 동작한다.

위 과정을 거치면 트리가 완성된다.

이후 전위탐색, 중위탐색, 후위탐색을 재귀함수로 구현해서 조건에 맞게 출력하면 된다.

코드

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

public class Main {
    static int[] dx = {0, 0, -1, 1};
    static int[] dy = {1, -1, 0, 0};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine());
        String[][] input = new String[n][3];
        ArrayList<Node> tree = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            input[i] = new String[3];
            String[] temp = br.readLine().split(" ");
            for (int j = 0; j < 3; j++) {
                input[i][j] = temp[j];
            }
            Node node = new Node(temp[0], temp[1], temp[2]);
            tree.add(node);
        }

        for (int i = 0; i < n; i++) {
            Node parent = tree.get(i);
            for (int j = i; j < n; j++) {
                Node child = tree.get(j);
                if (parent.lname.equals(child.value)) {
                    parent.left = child;
                    child.parent = parent;
                } else if (parent.rname.equals(child.value)) {
                    parent.right = child;
                    child.parent = parent;
                }
            }
        }

        preOrder(tree.get(0));
        System.out.println();
        inOrder(tree.get(0));
        System.out.println();
        postOrder(tree.get(0));
        System.out.println();

        br.close();
        bw.close();
    }

    private static void preOrder(Node node) {
        System.out.print(node.value);
        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);
        }
        System.out.print(node.value);
        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);
        }
        System.out.print(node.value);
    }
}

class Node {
    public Node parent;
    public Node left;
    public Node right;
    public String value;
    public String lname;
    public String rname;

    public Node() {
    }

    public Node(String value, String lname, String rname) {
        this.value = value;
        this.lname = lname;
        this.rname = rname;
    }
}