알고리즘 풀이 - 백준 1991(트리 순회, 트리)

 

관련글

 

트리 관련 포스팅은 여기를 참조

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

문제의 내용은 아래의 더보기를 클릭하여 참조

 

이진 트리를 전위, 중위, 후위 순회하는 결과를 출력하는 문제

 

 

2. 풀이

 

이진 트리를 Class 형태로 구성하여 각 정점을 연결시킨 후, 트리의 순회 방식에 따라 각각 순회하여 그 결과를 나타내는 문제이다.

각각의 노드 정보는 알파벳이 기준이므로 그 index를 활용하여 배열로 저장하였다.

 

기초 문제이므로 별도의 설명은 없고 트리에 대한 내용은 상단의 링크를 통해 확인하자.

 

 

3. 코드

 

아래의 코드를 통해 정답을 알아보자.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Queue;
import java.util.LinkedList;

public class Main{
    static int n;
    static Node[] alp;
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        alp = new Node[n+1];
        for(int i=1; i <= n; i++){
            alp[i] = new Node((char)('A' + i-1));
        }
        
        String[] line = null;
        for(int i=1; i <= n; i++){
            line = br.readLine().split(" ");
            int parent_idx = line[0].charAt(0) - 'A' + 1;
            
            char left = line[1].charAt(0);
            if(left != '.'){
                int left_idx = left - 'A' + 1;
                alp[parent_idx].left = left_idx;
                alp[left_idx].parent = parent_idx;
            }
            
            char right = line[2].charAt(0);
            if(right != '.'){
                int right_idx = right - 'A' + 1;
                alp[parent_idx].right = right_idx;
                alp[right_idx].parent = parent_idx;
            }
        }
        preOrder(alp[1]);
        sb.append("\n");
        inOrder(alp[1]);
        sb.append("\n");
        postOrder(alp[1]);
        
        System.out.println(sb);
        br.close();
    }
    
    // 전위 순회
    private static void preOrder(Node node){
        if(node == null) return;
        sb.append(node.value);
        preOrder(alp[node.left]);
        preOrder(alp[node.right]);
    }
    
    // 중위 순회
    private static void inOrder(Node node){
        if(node == null) return;
        inOrder(alp[node.left]);
        sb.append(node.value);
        inOrder(alp[node.right]);
    }
    
    // 후위 순회
    private static void postOrder(Node node){
        if(node == null) return;
        
        postOrder(alp[node.left]);
        postOrder(alp[node.right]);
        sb.append(node.value);
    }
}
class Node{
    int parent;
    int left;
    int right;
    char value;
    public Node(char value){
        this.parent = 0;
        this.left = 0;
        this.right = 0;
        this.value = value;
    }
}

 

 

읽어주셔서 감사합니다. 오류가 있으면 지적해주시면 반영하겠습니다.