[BOJ] 1991 - 트리 순회 (Java)

알고리즘 분류

• 트리

• 재귀

1. 문제

---

2. 트리 순회 review

2.1. 전위 순회 (Preorder Traversal)

• 서브 트리의 루트를 먼저 확인한 후에 자식 노드를 확인

• root 먼저 방문

• 왼쪽 서브트리 전위 순회

• 오른쪽 서브트리 전위 순회

2.2. 중위 순회 (Inorder Traversal)

• 왼쪽 자식 노드, 루트 노드, 오른쪽 자식 노드 순으로 값을 확인

• 왼쪽 서브트리 중위 순회

• 현재 노드 방문

• 오른쪽 서브트리 중위 순회

2.3. 후위 순회 (Postorder Traversal)

• 자식 노드를 모두 확인한 후에 루트 노드를 확인

• 왼쪽 서브트리 후위 순회

• 오른쪽 서브트리 후위 순회

• 현재 노드 방문

---

3. 풀이

3.1. Node class

• 이진 트리의 노드를 나타냄

• value: 값

• left: 왼쪽 child node

• right: 오른쪽 child node

static class Node{
    char value;
    Node left;
    Node right;

    Node(char value, Node left, Node right){
        this.value = value;
        this.left = left;
        this.right = right;
    }
}

3.2. 전역 변수 및 루트 노드 초기화

• cnt: 노드 수

• head: 루트 노드. 초기에 'A' 값을 가지는 노드로 초기화

static int n;
static Node head = new Node('A',null,null);

3.3. insertNode Method

• 루트 노드의 temp에서 지정된 root 값을 가진 노드를 찾은 뒤, 해당 노드의 왼쪽 자식과 오른쪽 자식에 새로운 노드를 추가

• 입력값으로 받은 root, left, right에 따라 새로운 노드를 생성하거나(if) null을 할당(else)

• 재귀적으로 왼쪽 서브 트리와 오른쪽 서브트 리를 탐색하면서 노드를 추가(insertNode)

static void insertNode(Node temp, char root,char left, char right) {
    //root 인가?
    if(temp.value==root) {
        //child node== . -> null, 아니면 new node 생성.
        temp.left=(left=='.'? null:new Node(left,null,null));
        temp.right=(right=='.'? null:new Node(right,null,null));
    }
    else {
        if(temp.left != null) insertNode(temp.left, root, left, right);
        if(temp.right != null) insertNode(temp.right, root, left, right);
    }
}

3.4. 순회 Methods (preOrder, inOrder, postOrder):

• 전위 순회, 중위 순회, 후위 순회 수행

• 노드가 null이 아닐 때까지 재귀적으로 수행

//전위 순회
static void preOrder(Node n) {
    if(n==null)	return;
    System.out.print(n.value);
    preOrder(n.left);
    preOrder(n.right);

}

//중위 순회
static void inOrder(Node n) {
    if(n==null)	return;
    inOrder(n.left);
    System.out.print(n.value);
    inOrder(n.right);

}

//후위 순회
static void postOrder(Node n) {
    if(n==null)	return;
    postOrder(n.left);
    postOrder(n.right);
    System.out.print(n.value);
}

3.5. main

• 트리의 노드 수 N scan

Scanner sc=new Scanner(System.in);
cnt = Integer.parseInt(sc.nextLine());

• N개의 줄에 대해 루트 노드, 왼쪽 자식, 오른쪽 자식 정보 scan하면서 insertNode 메서드를 호출하여 트리 구성

for(int i=0;i<cnt;i++) {
    String [] str = sc.nextLine().split(" ");
    char root = str[0].charAt(0);
    char left = str[1].charAt(0);
    char right = str[2].charAt(0);
    insertNode(head,root,left,right);
}

• 전위 순회, 중위 순회, 후위 순회 method를 호출 및 결과 출력

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

---

4. 전체코드

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

public class BOJ_1991 {
//    이진 트리 입력
//    전위 순회, 중위 순회, 후위 순회 결과 출력

//    Node class
    static class Node{
        char value;
        Node left;
        Node right;

        Node(char value, Node left, Node right){
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }

    static int cnt;
    static Node head = new Node('A',null,null);

    static void insertNode(Node temp, char root,char left, char right) {
        //root 인가?
        if(temp.value==root) {
            //child node== . -> null, 아니면 new node 생성.
            temp.left=(left=='.'? null:new Node(left,null,null));
            temp.right=(right=='.'? null:new Node(right,null,null));
        }
        else {
            if(temp.left != null) insertNode(temp.left, root, left, right);
            if(temp.right != null) insertNode(temp.right, root, left, right);
        }
    }

    static void preOrder(Node n) {
        if(n==null)	return;
        System.out.print(n.value);
        preOrder(n.left);
        preOrder(n.right);

    }
    static void inOrder(Node n) {
        if(n==null)	return;
        inOrder(n.left);
        System.out.print(n.value);
        inOrder(n.right);

    }
    static void postOrder(Node n) {
        if(n==null)	return;
        postOrder(n.left);
        postOrder(n.right);
        System.out.print(n.value);

    }

    public static void main(String[] args) throws IOException {
        Scanner sc=new Scanner(System.in);
        cnt = Integer.parseInt(sc.nextLine());

        for(int i=0;i<cnt;i++) {
            String [] str = sc.nextLine().split(" ");
            char root = str[0].charAt(0);
            char left = str[1].charAt(0);
            char right = str[2].charAt(0);
            insertNode(head,root,left,right);
        }

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

    }
}