[BOJ] 1991번 : 트리 순회

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

 

순회만 하는것이 아니라 node를 직접 만들어서 풀어야한다.

node를 어떻게 연결 지어서 만들어야할까 고민하다가 node 만드는 부분을 답을 봤다...ㅠ

static Node head = new Node("A", null, null);

 

 

문제에서는 "항상 A가 루트 노드가 된다" 라고 명시되어 있다.

그래서 처음에 head는 "A"로 해두고, 입력을 받을 때 마다 insert 해주었다.

for(int i=0;i<n;i++) {
    st = new StringTokenizer(br.readLine());
    String root = st.nextToken();
    String left = st.nextToken();
    String right = st.nextToken();

    insertNode(head, root, left, right);
}

 

 

만약에 root (A) 랑 같다면 새로운 node를 생성해주고, 다르다면 A 노드의 자식 노드일 것이다.

그러므로 입력받은 값에 따라 삽입해주면 된다.

static void insertNode(Node node, String root, String left, String right) {
    if(node.data.equals(root)) {
        node.left = (left.equals(".") ? null : new Node(left, null, null));
        node.right = (right.equals(".") ? null : new Node(right, null, null));
    }else {
        if(node.left != null) insertNode(node.left, root, left, right);
        if(node.right != null) insertNode(node.right, root, left, right);
    }
}

 

순회하는거는 간단하게 재귀를 사용해주면 된다. 전위 순회일 때는 root 먼저, 중위 순회일 때는 root가 중간에, 후위 순회일 때는 root를 가장 나중에 출력해주면 된다.

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

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

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

 

음 트리는 정말 오랜만ㅇ에 풀어본다...사실 며칠전에 풀어야 했는데, 이거 원 뽀로로도 아니고 노는게 이렇게 재밌을 수가 있나...오늘부터 다시...알고리즘 1개씩 풀어보자! 아래는 전체 코드다.

[전체코드]

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

public class Solution {
    static Node head = new Node("A", null, null);

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

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

        for(int i=0;i<n;i++) {
            st = new StringTokenizer(br.readLine());
            String root = st.nextToken();
            String left = st.nextToken();
            String right = st.nextToken();

            insertNode(head, root, left, right);
        }

        preOrder(head);
        System.out.println();
        inOrder(head);
        System.out.println();
        postOrder(head);
        System.out.println();

    }

    static void insertNode(Node node, String root, String left, String right) {
        if(node.data.equals(root)) {
            node.left = (left.equals(".") ? null : new Node(left, null, null));
            node.right = (right.equals(".") ? null : new Node(right, null, null));
        }else {
            if(node.left != null) insertNode(node.left, root, left, right);
            if(node.right != null) insertNode(node.right, root, left, right);
        }
    }

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

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

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

class Node{
    String data;
    Node left;
    Node right;

    Node(String data, Node left, Node right) {
        this.data = data;
        this.left = left;
        this.right = right;
    }
}

 

참고)

https://velog.io/@gandi0330/Java-%EB%B0%B1%EC%A4%80-%ED%8A%B8%EB%A6%AC-%EC%88%9C%ED%9A%8C-1991%EB%B2%88

[Java] 백준 / 트리 순회 / 1991번

https://banjjak1.tistory.com/44

[Java] 트리 (Tree)와 이진트리 (Binary Tree)