백준-1991번/트리순회(java)

 

 

문제 이해

 

자바를 통해 트리를 구현하고 전위순회, 중위순회, 후위순회를 구현해 보았다.

파이썬으로는 구현해본 경험이 있지만 자바로는 처음 구현해보아서 약간 생소했다. 

 

이 문제를 풀기 위해서 가장 중요한 것은 노드를 삽입을 구현하는 것이다.

 

문제 해결

 

우선 트리를 구현하기 위해서 Node 클래스를 만들어 준다.

 

필드값

1) data ==> 노드가 가지고 있는 데이터

2) left ==> 왼쪽 자식 노드

3) right ==> 오른쪽 자식 노드

 

static class Node{
   private char data;
   private Node left;
   private Node right;
    Node(char data) {
        this.data = data;
        this.left = null;
        this.right = null;
    }
        public Node(char data, Node left, Node right){
           this.data=data;
            this.left=left;
            this.right=right;
        }

}

 

 

그리고 구현하면서 가장 어려웠던 insertNode 메서드이다.

public static void insertNode(Node tmp, char root, char left, char right){
    if(tmp==null){
        return;
    }
    if(tmp.data==root){
        if(left!='.'){
            tmp.left=new Node(left);
        }
        if(right !='.'){
            tmp.right = new Node(right);
        }
    }
    else{
        insertNode(tmp.left,root,left,right);
        insertNode(tmp.right,root,left,right);
    }
}

루트 노트를 받아서 left와 right 노드를 계속 탐색하면서 내려가서 삽입 할 노드의 부모 노드를 찾으면 left나 right 노드로 넣어준다.

 

<전체 코드>

import java.util.Scanner;

public class Problem1991 {
    static Node head = new Node('A',null,null);

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        scanner.nextLine();
        for(int i=0; i<N; i++){
                String st = scanner.nextLine();
                insertNode(head,st.charAt(0),st.charAt(2),st.charAt(4));
        }

        preOrder(head);
        System.out.println();
        inOrder(head);
        System.out.println();
        postOrder(head);

    }

    static class Node{
       private char data;
       private Node left;
       private Node right;
        Node(char data) {
            this.data = data;
            this.left = null;
            this.right = null;
        }
            public Node(char data, Node left, Node right){
               this.data=data;
                this.left=left;
                this.right=right;
            }

    }
    public static void preOrder(Node node){
        if(node==null){
            return;
        }
        else{
            System.out.print(node.data);
            preOrder(node.left);
            preOrder(node.right);
        }
    }
    public static void inOrder(Node node){
        if(node==null){
            return;
        }
        else{
            inOrder(node.left);
            System.out.print(node.data);
            inOrder(node.right);
        }
    }

    public static void postOrder(Node node){
        if(node==null){
            return;
        }
        else{
            postOrder(node.left);
            postOrder(node.right);
            System.out.print(node.data);
        }
    }
    public static void insertNode(Node tmp, char root, char left, char right){
        if(tmp==null){
            return;
        }
        if(tmp.data==root){
            if(left!='.'){
                tmp.left=new Node(left);
            }
            if(right !='.'){
                tmp.right = new Node(right);
            }
        }
        else{
            insertNode(tmp.left,root,left,right);
            insertNode(tmp.right,root,left,right);
        }
    }

}