자바 백준 1991번 문제 : 트리 순회

문제 출처 : https://www.acmicpc.net/problem/1991

1991번: 트리 순회

 

 

문제 :

 

소스코드 :

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

class Node {
    char value;
    Node lt, rt;
    Node(char value, Node lt, Node rt) {
        this.value = value;
        this.lt = lt;
        this.rt = rt;
    }
}
public class Main
{
    Node root;
    public void toNode(Node node, char value, char lt, char rt) {
        if (node.value == value) {
            if (lt == '.') node.lt = null;
            else node.lt = new Node(lt, null, null);
            if (rt == '.') node.rt = null;
            else node.rt = new Node(rt, null, null);
        }
        else {
            if (node.lt != null) toNode(node.lt, value, lt, rt);
            if (node.rt != null) toNode(node.rt, value, lt, rt);
        }
    }
    // 전위 순회
    public void preOrder(Node root) {
        if (root == null) return;
        else {
            System.out.print(root.value);
            preOrder(root.lt);
            preOrder(root.rt);
        }
    }
    // 중위 순회
    public void inOrder(Node root) {
        if (root == null) return;
        else {
            inOrder(root.lt);
            System.out.print(root.value);
            inOrder(root.rt);
        }
    }
    // 후위 순회
    public void postOrder(Node root) {
        if (root == null) return;
        else {
            postOrder(root.lt);
            postOrder(root.rt);
            System.out.print(root.value);
        }
    }
    public static void main(String[] args) throws IOException {
        Main tree = new Main();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        tree.root = new Node('A', null, null);
        int n = Integer.parseInt(br.readLine());
        while(n-->0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            char value = st.nextToken().charAt(0);
            char lt = st.nextToken().charAt(0);
            char rt = st.nextToken().charAt(0);
            tree.toNode(tree.root, value, lt, rt);
        }
        tree.preOrder(tree.root);
        System.out.println();
        tree.inOrder(tree.root);
        System.out.println();
        tree.postOrder(tree.root);
    }
}

 

노드 생성과 순회 모두 재귀를 이용해 해결하였다.