이진 트리의 순회

종류

중위 순회 (in-order): 왼쪽 자식노드(L), 내 노드(P), 오른쪽 자식노드(R) 순서로 방문한다.
전위 순회 (pre-order): 내 노드(P), 왼쪽 자식노드(L), 오른쪽 자식노드(R) 순서로 방문한다.
후위 순회 (post-order) : 왼쪽 자식노드(L), 오른쪽 자식노드(R), 내 노드(P) 순서로 방문한다.

 

 

문제

루트가 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

 

 

코드

Java

import java.util.Scanner;

public class Main {
    private static Tree[] trees = null;

    private static class Tree {
        private int left = -1, right = -1, root;

        public int getLeft() {
            return left;
        }

        public void setLeft(int left) {
            this.left = left;
        }

        public int getRight() {
            return right;
        }

        public void setRight(int right) {
            this.right = right;
        }

        public int getRoot() {
            return root;
        }

        public void setRoot(int root) {
            this.root = root;
        }


        public Tree() {
        }

        public Tree(int root) {
            this.root = root;
        }


        public String preorder() {
            String result = "";

            result += root;
            if (left != -1) {
                if (!result.equals("")) result += " ";
                result += trees[left].preorder();
            }
            if (right != -1) {
                if (!result.equals("")) result += " ";
                result += trees[right].preorder();
            }

            return result;
        }

        public String inorder() {
            String result = "";

            if (left != -1) {
                if (!result.equals("")) result += " ";
                result += trees[left].inorder();
            }
            if (!result.equals("")) result += " ";
            result += root;
            if (right != -1) {
                if (!result.equals("")) result += " ";
                result += trees[right].inorder();
            }

            return result;
        }

        public String postorder() {
            String result = "";

            if (left != -1) {
                if (!result.equals("")) result += " ";
                result += trees[left].postorder();
            }
            if (right != -1) {
                if (!result.equals("")) result += " ";
                result += trees[right].postorder();
            }
            if (!result.equals("")) result += " ";
            result += root;

            return result;
        }
    }

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

        int size = Integer.parseInt(scan.nextLine());
        trees = new Tree[size];

        for (int i = 0; i < size; i++) {
            String line = scan.nextLine();
            String[] values = line.split(" ");

            int index = Integer.parseInt(values[0]);
            int left = Integer.parseInt(values[1]);
            int right = Integer.parseInt(values[2]);

            if (trees[index] == null) {
                trees[index] = new Tree(index);
            }
            trees[index].setLeft(left);
            trees[index].setRight(right);
        }

        System.out.println(trees[0].preorder());
        System.out.println(trees[0].inorder());
        System.out.println(trees[0].postorder());
    }
}