백준 - 트리 섹션 | 1991번. 트리 순회 (전위, 중위, 후위) DFS

23.03.20 문풀

1991번. 트리 순회 (전위, 중위, 후위) DFS

입력

첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파벳 대문자로 매겨지며, 항상 A가 루트 노드가 된다. 자식 노드가 없는 경우에는 .으로 표현한다.

출력

첫째 줄에 전위 순회, 둘째 줄에 중위 순회, 셋째 줄에 후위 순회한 결과를 출력한다. 각 줄에 N개의 알파벳을 공백 없이 출력하면 된다.

내 코드

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

/* 1991번. 트리 순회
이진 트리를 입력받아 전위 순회(preorder traversal)
     중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 프로그램을 작성하시오.
*/

class Node {
    char data;
    Node left;
    Node right;

    Node(char data) {
        this.data = data;
    }
}

class Tree {
    Node root; //루트 노드 처음엔 null 상태 

    public void createNode(char data, char leftData, char rightData) {
        if(root == null) { //아무것도 없는 초기 상태 - A 루트 노드 생성 
            root = new Node(data);

            //좌우 값이 있는 경우에만 노드 생성 
            if(leftData != '.') { 
                root.left = new Node(leftData);
            }
            if(rightData != '.') {
                root.right = new Node(rightData);
            }
        } else { //초기상태가 아니면 어디에 들어가야할지 찾아야함 - A 루트 노드 이후 
            searchNode(root, data, leftData, rightData);
        }
    }

    //여기에서 root는 매개 변수로 들어온 로컬변수 root임을 주의 
    public void searchNode(Node root, char data, char leftData, char rightData) { 
        if(root == null) { //도착한 노드가 null이면 재귀 종료 - 찾을(삽입할) 노드 X
            return;
        } else if(root.data == data) { //들어갈 위치를 찾았다면 
            if(leftData != '.') { //.이 아니라 값이 있는 경우에만 좌우 노드 생성 
                root.left = new Node(leftData);
            }
            if(rightData != '.') {
                root.right = new Node(rightData);
            }
        } else { //아직 찾지못했고 탐색할 노드가 남아 있다면 
            searchNode(root.left, data, leftData, rightData); //왼쪽 재귀 탐색 
            searchNode(root.right, data, leftData, rightData); //오른쪽 재귀 탐색 
        }
    }

    // 전위순회 : 루트 -> 좌 -> 우 
    public void preorder(Node root){
        System.out.print(root.data); //먼저 가운데 출력
        if(root.left!=null) preorder(root.left); //그 다음 왼쪽
        if(root.right!=null) preorder(root.right); //마지막 오른쪽
    }

    // 중위순회 : 좌 -> 루트 -> 우
    public void inorder(Node root){
        if(root.left!=null) inorder(root.left); //왼쪽 먼저
        System.out.print(root.data); //그 다음 중앙 출력
        if(root.right!=null) inorder(root.right); //마지막으로 오른쪽
    }

    // 후위순회 : 좌 -> 우 -> 루트 
    public void postorder(Node root){
        if(root.left!=null) postorder(root.left); //왼쪽 먼저
        if(root.right!=null) postorder(root.right); //그 다음 오른쪽
        System.out.print(root.data);
    }

}

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        Tree tree = new Tree();

        for(int i = 0; i < N; i++) {
            char[] data;
            data = br.readLine().replaceAll(" ", "").toCharArray();
            tree.createNode(data[0], data[1], data[2]);
        }

        //전위 순회 
        tree.preorder(tree.root);
        System.out.println();

        //중위 순회 
        tree.inorder(tree.root);
        System.out.println();

        //후위 순회 
        tree.postorder(tree.root);

        br.close();
    }
}

---