백준 1991번 : 트리 순회 java

이 문제는 트리를 만들어서 노드를 삽입 후 전위 순회, 중위 순회, 후위 순회한 결과를 출력하는 문제입니다.

전위 순회와 중위 순회, 후위 순회에 대한 설명은 네이버 백과사전에 자세히 나와있습니다.

링크를 아래에 두도록 하겠습니다.

https://terms.naver.com/entry.naver?docId=2270429&cid=51173&categoryId=51173

이진 트리

 

이제 코드를 보여드리겠습니다.

---

import java.io.*;

public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        Tree tree = new Tree();

        for(int i = 0; i<N; i++){
            String[] input = br.readLine().split(" ");

            tree.createNode(input[0], input[1], input[2]);
        }

        tree.preOrder(tree.root);
        System.out.println();

        tree.inOrder(tree.root);
        System.out.println();

        tree.postOrder(tree.root);
        System.out.println();
    }
}

class Tree{
    Node root = new Node(".");

    void createNode(String mid, String left, String right){
        if(root.data.equals(".")){
            if(!mid.equals("."))
                root = new Node(mid);
            if(!left.equals("."))
                root.left = new Node(left);
            if(!right.equals("."))
                root.right = new Node(right);
        }

        else find(root, mid, left, right);
    }

    void find(Node node, String mid, String left, String right){
        if(node == null)
            return;

        else if(mid.equals(node.data)){
            if(!left.equals("."))
                node.left = new Node(left);
            if(!right.equals("."))
                node.right = new Node(right);
        }

        find(node.left, mid, left, right);
        find(node.right, mid, left, right);
    }

    void preOrder(Node node){
        System.out.print(node.data);

        if(node.left != null)
            preOrder(node.left);

        if(node.right != null)
            preOrder(node.right);
    }

    void inOrder(Node node){
        if(node.left != null)
            inOrder(node.left);

        System.out.print(node.data);

        if(node.right != null)
            inOrder(node.right);
    }

    void postOrder(Node node){
        if(node.left != null)
            postOrder(node.left);

        if(node.right != null)
            postOrder(node.right);

        System.out.print(node.data);
    }
}

class Node{
    String data;
    Node left, right;

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

저는 Tree class를 만들어서 이 안에서 Node를 이용한 작업들을 진행하였습니다.

createNode에서 root가 "."이면 null로 취급하여 새로운 노드를 만들어 주었고, root가 null이 아니면 find함수를
실행하였습니다.

find 함수는 mid와 Node의 data값을 비교하여 같으면 그 아래에 노드들을 추가하도록 만들었습니다.