[JAVA]BOJ 1991, 트리 순회

트리를 구현하고 순회하는 단순한 문제이다.

 

트리를 구현할때.. 클래스가 3개 필요하다. 메인, node, binaryTree

 

1. node 클래스

public class Node {
    char data;
    Node left;
    Node right;

    Node(char data){
        this.data = data;
    }
}

단순하게 노드를 구현한다. 자기자신과 왼쪽노드, 오른쪽노드를 가진다.

 

 

2. BinaryTree 클래스

import java.util.HashMap;

public class BinaryTree {
    private Node root; // 루트 노드
    private HashMap<Character, Node> nodes; // 각 노드를 저장하는 맵, 간선 역할

    public BinaryTree() {
        nodes = new HashMap<>();
    }

    public Node getRoot(){ // 루트 반환
        return root;
    }

    public void add(char parent, char left, char right){
        if(!nodes.containsKey(parent)) // 부모노드가 존재하지 않으면 생성
            nodes.put(parent, new Node(parent));

        Node parentNode = nodes.get(parent); // 부모노드 저장

        if(left != '.'){ // 왼쪽 자식이 있다면
            parentNode.left = new Node(left); // 부모노드에 왼쪽노드 생성해서 연결하고
            nodes.put(left, parentNode.left); // nodes 맵에 저장
        }

        if(right != '.'){ // 오른쪽 자식이 있다면
            parentNode.right = new Node(right); // 부모노드에 오른쪽노드 생성해서 연결하고
            nodes.put(right, parentNode.right); // nodes 맵에 저장
        }

        if(root == null) // 루트 지정하기
            root = parentNode;
    }

    public void preorder(Node node){ // 전위 순회
        if(node == null) return;
        System.out.print(node.data);
        preorder(node.left);
        preorder(node.right);
    }

    public void inorder(Node node){ // 중위 순회
        if(node == null) return;
        inorder(node.left);
        System.out.print(node.data);
        inorder(node.right);
    }

    public void postorder(Node node){ // 후위 순회
        if(node == null) return;
        postorder(node.left);
        postorder(node.right);
        System.out.print(node.data);
    }
}

해시맵이 연결해주는 간선 역할을 한다.

메소드는 루트를 반환하는 getRoot, 노드를 생성하고 연결하는 add, 순회방법 3가지 preorder, inorder, postorder 이렇게 구현했다.

 

3. 메인

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ1991 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N, i;
        BinaryTree tree = new BinaryTree();
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        for(i=0;i<N;i++){
            st = new StringTokenizer(br.readLine());
            tree.add(st.nextToken().charAt(0), st.nextToken().charAt(0), st.nextToken().charAt(0));
        }

        tree.preorder(tree.getRoot());
        System.out.println();

        tree.inorder(tree.getRoot());
        System.out.println();

        tree.postorder(tree.getRoot());
        System.out.println();
    }
}

메인에서는 문제에서 주어진대로 입력을 받고, tree.add를 호출해 노드를 만들고 연결시킨다. 그리고 세가지 방법으로 순회를 한다.