[Java] 백준 BOJ / 1991번: 트리 순회

트리 순회

문제

---

문제 설명

트리를 순회하는 세가지 방법

1. 전위 순회(Preorder)
   • 루트 -> 왼쪽 -> 오른쪽
2. 중위 순회(Inorder)
   • 왼쪽 -> 루트 -> 오른쪽
3. 후위 순회(Postorder)
   • 왼쪽 -> 오른쪽 -> 루트

이 세가지 방법으로 트리를 순회한 결과를 출력하는 문제이다.

문제에 주어지는 정보를 저장하기 위해 Node 라는 Class를 생성한 후에 저장되는 값과 자식 노드들을 저장하는 두개의 Node 변수를 설정하였다.

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

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

위 Node 클래스를 기반으로 입력을 받고 재귀를 사용해서 트리를 순회하도록 하면 된다.

예제를 들어서 전위 순회만 설명을 하도록 하겠다.

---

코드 설명

public static void preorder(Node node) {
	if (node == null) {
		return;
	}
	System.out.print(node.value);
	preorder(node.left);
	preorder(node.right);
}

코드만 봐도 이해가 되긴 하겠지만 간단하게 설명을 하자면 다음과 같다.

함수의 인자로 받은 node에 대해서 만약 해당 node가 null 이라면 트리의 끝에 도달했다는 것이기 때문에 함수를 종료하고, 그렇지 않다면 전위 순회의 순서대로 루트를 출력을 하고 node의 왼쪽을 함수의 인자로 넘겨주고 그 다음은 node의 오른쪽을 함수의 인자로 넘겨주면 되는 것이다.

위에 설명한 내용을 기반대로 작성한 전체 코드는 아래와 같다.

---

코드

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

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

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

    static int n;
    static Node[] tree;


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

        tree = new Node[n + 1];

        //트리 만들기
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            char parent = st.nextToken().charAt(0);
            char leftNode = st.nextToken().charAt(0);
            char rightNode = st.nextToken().charAt(0);

            if (tree[parent - 'A'] == null) {
                tree[parent - 'A'] = new Node(parent);
            }

            if (leftNode != '.') {
                tree[leftNode - 'A'] = new Node(leftNode);
                tree[parent - 'A'].left = tree[leftNode - 'A'];
            }

            if (rightNode != '.') {
                tree[rightNode - 'A'] = new Node(rightNode);
                tree[parent - 'A'].right = tree[rightNode - 'A'];
            }
        }

        preorder(tree[0]);
        System.out.println();

        inorder(tree[0]);
        System.out.println();

        postorder(tree[0]);
        System.out.println();
    }

    public static void preorder(Node node) {
        if (node == null) {
            return;
        }
        System.out.print(node.value);
        preorder(node.left);
        preorder(node.right);
    }

    public static void inorder(Node node) {
        if (node == null) {
            return;
        }
        inorder(node.left);
        System.out.print(node.value);
        inorder(node.right);
    }

    public static void postorder(Node node) {
        if (node == null) {
            return;
        }
        postorder(node.left);
        postorder(node.right);
        System.out.print(node.value);
    }
}