[백준] 1991번 - 트리 순회

1991번: 트리 순회

 

 

이진 트리란 하나의 노드가 가질 수 있는 자식 노드의 수가 최대 2개로 제한되어 있는 트리구조로 자식 노드를 왼쪽 자식 노드와 오른쪽 자식 노드라고 부른다. 

 

트리를 사용하는 경우 보통은 트리를 순회하며 찾고자 하는 값을 탐색하기 때문에 해당 자료구조를 사용하기 위해서 순회하는 방법에 대해서는 기본적으로 알아두면 좋다. 트리를 순회하는 방법은 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal) 3가지가 있다. 

 

 

전위 순회 방문 순서

 

중위 순회 방문 순서

후위 순회 방문 순서

 

각 순회 방식의 방문 순서는 위 그림과 같다.

 

 

 

전위, 중위, 후위 순회에 대한 기본 개념을 알아보았으니 다음은 구현할 차례이다. 트리를 이중배열에 저장하고 재귀함수를 사용하면 구현할 수 있다. 우선 출력에 사용할 StringBuilder sb객체를 하나 생성한다. 

전위 순회의 경우 현재 노드를 일단 sb에 넣고 왼쪽 자식노드, 오른쪽 자식노드를 차례대로 재귀호출하면된다.

중위 순회의 경우 왼쪽 자식 노드부터 방문해야 하므로 왼쪽 자식 노드 재귀호출, 현재 노드를 sb에 넣고 오른쪽 자식노드를 재귀호출한다. 

후위 순회의 경우 왼쪽 자식 노드 재귀호출, 오른쪽 자식노드 재귀호출 그리고 현재 노드를 sb에 넣는다.

 

추가로 이번 문제에서 입력을 받을 때 문자열의 공백을 제거하는 정규 표현식을 사용해보았다.

String before = "A B C";

// "\\s"은 공백(whitespace)을 의미하는 정규 표현식이다.
String after = before.replaceAll("\\s", "");

System.out.println(after);

// 출력
ABC

 

 

 

 

 

이중 배열에 트리를 저장한 풀이

import java.util.*;

public class Main {
    
    static char[][] link;
    static StringBuilder sb = new StringBuilder();
    
    public static void main (String[] args) {
        
        Scanner sc = new Scanner(System.in);
        
        int N = Integer.parseInt(sc.nextLine());
        
        link = new char[N][2];
        
        char[] inputChar = null;
        for (int i=0; i<N; i++) {
            inputChar = sc.nextLine().replaceAll("\\s", "").toCharArray();
            int parent = inputChar[0] - 'A';
            link[parent][0] = inputChar[1];
            link[parent][1] = inputChar[2];
        }
        
        preOrder(charToInt('A'));
        sb.append("\n");
        inOrder(charToInt('A'));
        sb.append("\n");
        postOrder(charToInt('A'));
        sb.append("\n");
        
        System.out.println(sb);
        
        sc.close();
    }
    
    static void preOrder (int node) {
        
        char left = link[node][0];
        char right = link[node][1];
        
        sb.append(intToChar(node));
        if (left != '.') preOrder(charToInt(left));
        if (right != '.') preOrder(charToInt(right));
    }
    
    static void inOrder (int node) {
        
        char left = link[node][0];
        char right = link[node][1];
        
        if (left != '.') inOrder(charToInt(left));
        sb.append(intToChar(node));
        if (right != '.') inOrder(charToInt(right));
    }
    
    static void postOrder (int node) {
        
        char left = link[node][0];
        char right = link[node][1];
        
        if (left != '.') postOrder(charToInt(left));
        if (right != '.') postOrder(charToInt(right));
        sb.append(intToChar(node));
    }
    
    static char intToChar (int node) {
        return (char) (node + 'A');
    }
    static int charToInt (char c) {
        return c - 'A';
    }
}

 

 

 

 

처음에는 이중 배열에 트리를 저장하는 방식으로 풀이하였는데, 다른 사람들의 풀이를 확인해보니 각 노드에 대한 왼쪽, 오른쪽 자식 노드에 대한 정보를 저장하는 객체를 별도로 생성하여 해결한 것을 발견하였다. 

 

순회하는 재귀함수 구현은 같지만 Tree 객체에서 각 노드에 대한 정보를 저장하는 방법이 흥미로워서 해당 방법으로 풀이한 코드도 함께 기록한다.

 

 

 

import java.util.*;

class Node {
    char node;
    Node left, right;
    public Node (char node) {
        this.node = node;
    }
}

class Tree {
    
    StringBuilder sb;
    Node root;
    
    public Tree (char node) {
        root = new Node(node);
    }
    
    public void insert (Node parent, char data, char left_data, char right_data) {
        
        if (parent == null) return;
        
        if (parent.node == data) {
            if (left_data != '.')
                parent.left = new Node(left_data);
            if (right_data != '.')
                parent.right = new Node(right_data);
        }
        else {
            insert(parent.left, data, left_data, right_data);
            insert(parent.right, data, left_data, right_data);
        }
    }
    
    public void resetPrintObj () {
    	sb = new StringBuilder();
    }
    public String print () {
    	return String.valueOf(sb);
    }
    
    
    public void preOrder (Node n) {
        
        if (n == null) return;
        
        sb.append(n.node);
        preOrder(n.left);
        preOrder(n.right);
    }
    
    public void inOrder (Node n) {
        
        if (n == null) return;
        
        inOrder(n.left);
        sb.append(n.node);
        inOrder(n.right);
    }
    
    public void postOrder (Node n) {
        
        if (n == null) return;
        
        postOrder(n.left);
        postOrder(n.right);
        sb.append(n.node);
    }
}

public class Main {
    
    public static void main (String[] args) {
        
        Scanner sc = new Scanner(System.in);
        
        int N = sc.nextInt();
        
        Tree tree = new Tree('A');
        
        for (int i=0; i<N; i++)
            tree.insert(tree.root, sc.next().charAt(0), sc.next().charAt(0), sc.next().charAt(0));
        
        tree.resetPrintObj();
        tree.preOrder(tree.root);
        System.out.println(tree.print());
        
        tree.resetPrintObj();
        tree.inOrder(tree.root);
        System.out.println(tree.print());
        
        tree.resetPrintObj();
        tree.postOrder(tree.root);
        System.out.println(tree.print());
        
        
        sc.close();
    }
}