5-1: 트리순회 결과 출력하기

트리순회 결과 출력하기

 

문제

---

루트가 0인 이진트리가 주어질 때, 이를 전위순회, 중위순회, 후위순회한 결과를 각각 출력하는 프로그램을 작성하시오. 아래 그림은 이진트리의 예제와, 이 이진트리를 전위순회, 중위순회, 후위순회 한 결과를 나타낸다.

 

입력

---

첫 번째 줄에 트리의 노드 개수 n이 주어진다. ( 1 ≤ n ≤ 100 ) 두 번째 줄부터 트리의 정보가 주어진다. 각 줄은 3개의 숫자 a, b, c로 이루어지며, 그 의미는 노드 a의 왼쪽 자식노드가 b, 오른쪽 자식노드가 c라는 뜻이다. 자식노드가 존재하지 않을 경우에는 -1이 주어진다.

 

출력

---

첫 번째 줄에 전위순회, 두 번째 줄에 중위순회, 세 번째 줄에 후위순회를 한 결과를 출력한다.

 

예제 입력

6
0 1 2
1 3 4
2 -1 5
3 -1 -1
4 -1 -1
5 -1 -1

예제 출력

0 1 3 4 2 5
3 1 4 0 2 5
3 4 1 5 2 0

import java.util.Scanner;

public class TreeTraversal {

    /**
     *
     * 문제: 루트가 0인 이진트리가 주어질 때, 이를 전위순회, 중위순회, 후위순회한 결과를 각각 출력하는 프로그램을 작성하시오. 아래 그림은 이진트리의 예제와, 이 이진트리를 전위순회, 중위순회, 후위순회 한 결과를 나타낸다.
     *
     *
     * 입력:
     * 첫 번째 줄에 트리의 노드 개수 n이 주어진다. ( 1 ≤ n ≤ 100 )
     * 두 번째 줄부터 트리의 정보가 주어진다. 각 줄은 3개의 숫자 a, b, c로 이루어지며, 그 의미는 노드 a의 왼쪽 자식노드가 b, 오른쪽 자식노드가 c라는 뜻이다. 자식노드가 존재하지 않을 경우에는 -1이 주어진다.
     *
     * 출력:
     * 첫 번째 줄에 전위순회, 두 번째 줄에 중위순회, 세 번째 줄에 후위순회를 한 결과를 출력한다.
     *
     * 예제 입력:
     * 6
     * 0 1 2
     * 1 3 4
     * 2 -1 5
     * 3 -1 -1
     * 4 -1 -1
     * 5 -1 -1
     *
     * 예제 출력:
     * 0 1 3 4 2 5
     * 3 1 4 0 2 5
     * 3 4 1 5 2 0
     *
     * @param args
     */

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        TreeNode[] nodes = new TreeNode[N];

        for (int i=0; i<N; i++){
            int curData = sc.nextInt();
            int leftData = sc.nextInt();
            int rightData = sc.nextInt();

            if (nodes[curData] == null){
                TreeNode node = new TreeNode(curData);
                nodes[curData] = node;
            }

            if (leftData == -1){
                nodes[curData].left = null;
            } else {
                if (nodes[leftData] == null){
                    TreeNode node = new TreeNode(leftData);
                    nodes[leftData] = node;
                    nodes[curData].left = nodes[leftData];
                }
            }

            if (rightData == -1){
                nodes[curData].right = null;
            } else{
                if (nodes[rightData] == null){
                    TreeNode node = new TreeNode(rightData);
                    nodes[rightData] = node;
                    nodes[curData].right = nodes[rightData];
                }
            }
        }

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

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

        postorder(nodes[0]);

    }

    private static void preorder(TreeNode node) {
        if (node == null) return;
        System.out.print(node.data +" ");
        preorder(node.left);
        preorder(node.right);
    }

    private static void inorder(TreeNode node) {
        if (node == null) return;
        inorder(node.left);
        System.out.print(node.data +" ");
        inorder(node.right);
    }

    private static void postorder(TreeNode node) {
        if (node == null) return;
        postorder(node.left);
        postorder(node.right);
        System.out.print(node.data +" ");
    }

    public static class TreeNode{
        int data;
        TreeNode left;
        TreeNode right;

        public TreeNode(int data){
            this.data = data;
        }
    }
}