BOJ) 트리 순회 (1991 번)

트리 순회

1991번: 트리 순회

 

이진 트리에 대한 개념을 알고 있다면 어렵지 않은 문제였다.

다만, 트리의 입력 정보가 포화 이진 트리인지, 완전 이진 트리인지, 정 이진 트리인지 보장해주지 않는다.

(트리에 대한 개념 설명은 이전 자료구조의 트리 포스팅을 참고)

그래서, 해당 노드의 값에 따라 정보를 입력해주어야 한다는게 핵심이었던 것 같다.

 

위의 입력 문제를 해결하기 위해서 append라는 메소드를 만들었다.

node의 vertex 값이 일치하는 node를 찾아 left, right를 만들어주었다.

add와 append를 나눈 이유는 node를 탐색하는 과정을 숨기기 위해서다. (그냥 그러고 싶었다..)

전위 순회, 중위 순회, 후위 순회에 따라 결과를 출력해주어야 하는데, 처음에는 각 3개의 메소드를 만드려고 했다.

하지만, 중복되는 코드를 굳이 만들필요가 있을까 싶어서 출력을 담당해줄 StringBuilder를 각 순회 방법마다 선언해주었다.

그리고, append하는 타이밍을 전위, 중위, 후위에 맞게 설정해주었다.

 

코드

 

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

public class TreeTraversal_1991 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        Tree tree = new Tree(st.nextToken().charAt(0), st.nextToken().charAt(0), st.nextToken().charAt(0));
        while(--n >0) {
            st = new StringTokenizer(br.readLine());
            tree.add(st.nextToken().charAt(0), st.nextToken().charAt(0), st.nextToken().charAt(0));
        }

        br.close();
        solution(tree);
    }

    private static void solution(Tree tree) {
        tree.print();
    }

}
class Tree {
    Node root;
    private StringBuilder preSB, inSB, postSB;
    private final char NULL = '.';

    public Tree(char vertex, char left, char right) {
        this.root = new Node(vertex);
        if(left != NULL) {
            this.root.left = new Node(left);
        }
        if(right != NULL) {
            this.root.right = new Node(right);
        }
    }

    public void add(char vertex, char left, char right) {
        this.append(this.root, vertex, left, right);
    }

    private void append(Node node, char vertex, char left, char right) {
        if(node == null) {
            return;
        } else if(node.vertex == vertex) {
            if(left != NULL) {
                node.left = new Node(left);
            }
            if(right != NULL) {
                node.right = new Node(right);
            }
        } else {
            append(node.left, vertex, left, right);
            append(node.right, vertex, left, right);
        }
    }

    public void print() {
        preSB = new StringBuilder();
        inSB = new StringBuilder();
        postSB = new StringBuilder();
        this.traversal(this.root);
        System.out.println(preSB.toString());
        System.out.println(inSB.toString());
        System.out.println(postSB.toString());
    }

    private void traversal(Node node) {
        if(node != null && node.vertex != NULL) {
            preSB.append(node.vertex);
            traversal(node.left);
            inSB.append(node.vertex);
            traversal(node.right);
            postSB.append(node.vertex);
        }
    }
    private class Node {
        char vertex;
        Node left, right;

        public Node(char vertex) {
            this.vertex = vertex;
        }
    }
}