1991번

https://www.acmicpc.net/problem/1991

1991번: 트리 순회

오늘은 트리의 기초인 트리순회 3가지에 대해 공부해보고 문제를 풀었다.

처음에는 1차원 배열로 시도하려고 했지만 어떤식으로 배열을 처리해야할지 감이 잡히지 않아서 클래스를 이용한 순회로 변경하였다..

이 문제를 풀기위해 알아야 할 것은 전위순회, 중위순회, 후위순회인데 전,중,후를 나누는 기준은 부모노드를 어디에 두느냐이다.

말 그대로 순회를 할때 부모노드를 제일먼저 탐색하고 왼쪽자식, 오른쪽 자식 순으로 가면 전위순회, 왼쪽 자식, 부모 노드, 오른쪽 자식 순으로 순회하면 중위순회, 왼쪽, 오른쪽 자식, 부모 노드 순으로 순회하면 후위 순회이다.

정리하면,

부모, 왼쪽, 오른쪽 - 전위 순회

왼쪽, 부모, 오른쪽 - 중위 순회

왼쪽, 오른쪽, 부모 - 후위 순회

 

따라서 재귀를 사용하여 탐색하면 된다.

중위 순회는 백트래킹을 생각해보면 이해가 쉬울 것이다.

 

그래서 메서드는 2가지로 나누었다.

root노드를 기반으로 트리를 만들기 위한 createTree와 노드의 위치를 찾기위한 search로 만들었고,

그 다음 3가지 전위, 중위, 후위 메서드를 구현했다.

 

트리 생성과 순회 과정에서 모두 재귀를 사용하였다.

생성과정에서는 입력받은 값들 중 부모 노드와 일치하는 값을 찾아서 왼쪽, 오른쪽이 비어있으면 채우고, 찾지 못하면 남은 노드들을 계속 확인하는 방식으로 했다.

순회는 위에서 설명한 순서대로 탐색하도록 했다.

 

package backjoon.b1991;

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

public class b1991 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        Node root = new Node("A");
        Tree g = new Tree(root);

        for(int i=0; i<N; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            String data = st.nextToken();
            String leftData = st.nextToken();
            String rightData = st.nextToken();
            g.creatTree(data,leftData,rightData);
        }
        g.preOrder(root);
        g.sb.append("\n");
        g.inOrder(root);
        g.sb.append("\n");
        g.postOrder(root);
        System.out.println(g.sb);
    }
}
class Tree{
    Node root;

    StringBuilder sb = new StringBuilder();
    public Tree(Node root) {
        this.root = root;
    }

    public void creatTree(String data, String leftData, String rightData){
        search(root,data,leftData,rightData);
    }
    public void search(Node node, String data, String leftData, String rightData){
        if(node==null){
            return;
        }
        else if (node.data.equals(data)) {
            if (node.left==null){
                node.left = new Node(leftData);//왼쪽 자식 없으면 채우기
            }
            if(node.right==null){
                node.right = new Node(rightData);//오른쪽 자식 없으면 채우기
            }
        }
        else {
            search(node.left,data,leftData,rightData);//노드의 왼쪽 자식 탐색
            search(node.right,data,leftData,rightData);//노드의 오른쪽 자식 탐색
        }
    }
    public void preOrder(Node node){
        if(node!=null){
            if(!node.data.equals("."))sb.append(node.data);
            if(node.left!=null)preOrder(node.left);
            if(node.right!=null)preOrder(node.right);
        }
    }//전위 순회
    public void inOrder(Node node){
        if(node!=null){
            if(node.left!=null)inOrder(node.left);
            if(!node.data.equals("."))sb.append(node.data);
            if(node.right!=null)inOrder(node.right);
        }
    }//중위 순회
    public void postOrder(Node node){
        if(node!=null){
            if(node.left!=null)postOrder(node.left);
            if(node.right!=null)postOrder(node.right);
            if(!node.data.equals("."))sb.append(node.data);
        }
    }//후위 순회
}
class Node{
    Node left;

    Node right;
    
    String data;

    public Node(String data) {
        this.data = data;
    }
}