[Java] 1991번 : 트리 순회

[peppermintt0504]

원본

문제 풀이

해당 문제는 노드에 대한 이해도와 순회에 대한 이해도를 높이기 좋은 문제이다. 노드를 입력 받아 해당 트리를 전위, 중위, 후위 순회로 출력하면 된다.

이 때 각 노드는 값이 아니라 문자로 이루어져 있어 각 노드를 Map에 저장해두어 노드를 삽입해야 한다.

아래는 Node 클래스이다. 노드는 생성시 노드의 값(알파벳)으로 저장하고 각 노드는 null로 비워둔다.

    public static class Node{
        String val;
        Node left;
        Node right;

        public Node() {}
        public Node(String val) {
            this.val = val;
            left = null;
            right = null;
        }

        public void setRight(Node r) {
            this.right = r;
        }

        public void setLeft(Node l) {
            this.left = l;
        }
    }

해당 노드 클래스를 통해 모든 입력을 받아 트리를 완성하면 된다. 이 때 처음 입력인 A는 root이다. 노드를 삽입하며 Map에 저장 되지 않은 노드를 꼭 저장 해야 한다. 그렇지 않으면 하위 노드의 주소를 알 방법이 없어지기 때문이다.

while(T-- > 0) {
            String[] temp = br.readLine().split(" ");

            Node tempNode;

            if(memo.containsKey(temp[0])) {
                tempNode= memo.get(temp[0]);
            }else {
                tempNode = new Node(temp[0]); 
                memo.put(temp[0],tempNode);
            }

            if(!temp[1].equals(".")) {
                if(memo.containsKey(temp[1])) {
                    tempNode.setLeft(memo.get(temp[1]));
                }else {
                    Node leftNode = new Node(temp[1]); 
                    tempNode.setLeft(leftNode);
                    memo.put(temp[1],leftNode);
                }
            }
            if(!temp[2].equals(".")) {
                if(memo.containsKey(temp[2])) {
                    tempNode.setRight(memo.get(temp[2]));
                }else {
                    Node rightNode = new Node(temp[2]); 
                    tempNode.setRight(rightNode);
                    memo.put(temp[2],rightNode);
                }
            }
        }

이제 입력 받은 트리를 각 순회로 출력을 해야 한다. 이 때 각 순회는 아래 방법과 같다.

전위 순회 : (루트) (왼쪽 자식) (오른쪽 자식) 중위 순회 : (왼쪽 자식) (루트) (오른쪽 자식) 후위 순회 : (왼쪽 자식) (오른쪽 자식) (루트) 해당 순서 별로 재귀 함수를 생성해준다.

public static void preorderTraversal(Node root) throws IOException {
        bw.write(root.val);
        if(root.left != null)preorderTraversal(root.left);
        if(root.right != null)preorderTraversal(root.right);
}

public static void inorderTraversal(Node root) throws IOException {
    if(root.left != null)inorderTraversal(root.left);
    bw.write(root.val);
    if(root.right != null)inorderTraversal(root.right);
}

public static void postorderTraversal(Node root) throws IOException {
    if(root.left != null)postorderTraversal(root.left);
    if(root.right != null)postorderTraversal(root.right);
    bw.write(root.val);
}
[풀이 코드](https://pepperminttt.tistory.com/79#%ED%--%--%EC%-D%B-%--%EC%BD%--%EB%--%-C)
import java.util.*;
import java.io.*;
public class Main {
    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    public static Map<String,Node> memo = new HashMap<>();

    public static class Node{
        String val;
        Node left;
        Node right;

        public Node() {}

        public Node(String val) {
            this.val = val;
            left = null;
            right = null;
        }

        public void setRight(Node r) {
            this.right = r;
        }

        public void setLeft(Node l) {
            this.left = l;
        }
    }

    public static void main(String[] args) throws IOException{

        int T = Integer.parseInt(br.readLine());

        while(T-- > 0) {
            String[] temp = br.readLine().split(" ");

            Node tempNode;

            if(memo.containsKey(temp[0])) {
                tempNode= memo.get(temp[0]);
            }else {
                tempNode = new Node(temp[0]); 
                memo.put(temp[0],tempNode);
            }

            if(!temp[1].equals(".")) {
                if(memo.containsKey(temp[1])) {
                    tempNode.setLeft(memo.get(temp[1]));
                }else {
                    Node leftNode = new Node(temp[1]); 
                    tempNode.setLeft(leftNode);
                    memo.put(temp[1],leftNode);
                }
            }
            if(!temp[2].equals(".")) {
                if(memo.containsKey(temp[2])) {
                    tempNode.setRight(memo.get(temp[2]));
                }else {
                    Node rightNode = new Node(temp[2]); 
                    tempNode.setRight(rightNode);
                    memo.put(temp[2],rightNode);
                }
            }
        }

        preorderTraversal(memo.get("A"));
        bw.write("\n");
        inorderTraversal(memo.get("A"));
        bw.write("\n");
        postorderTraversal(memo.get("A"));
        bw.flush();
        bw.close();
    }

    public static void preorderTraversal(Node root) throws IOException {
        bw.write(root.val);
        if(root.left != null)preorderTraversal(root.left);
        if(root.right != null)preorderTraversal(root.right);
    }

    public static void inorderTraversal(Node root) throws IOException {
        if(root.left != null)inorderTraversal(root.left);
        bw.write(root.val);
        if(root.right != null)inorderTraversal(root.right);
    }

    public static void postorderTraversal(Node root) throws IOException {
        if(root.left != null)postorderTraversal(root.left);
        if(root.right != null)postorderTraversal(root.right);
        bw.write(root.val);
    }
}