트리순회 / 숫자

트리순회 결과 출력하기

 

문제

---

루트가 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.ArrayList;
import java.util.Scanner;

public class Main {

    public static ArrayList<Node> box = new ArrayList<>();
    public static int count = 0;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        //총 몇개의 숫자를 입력 받을 것인지
        int a;
        int b = 1;
        int c = 0;

        Node node,leftNode,rightNode;
        int input;

        a = sc.nextInt();

        for(int i = 0 ; i < a ; i++) {
            input = sc.nextInt();
            node = findeNode(input);

            input = sc.nextInt();
            if(input != -1) {
                leftNode = findeNode(input);
                node.setLeftChild(leftNode);
            }

            input = sc.nextInt();
            if(input != -1) {
                rightNode = findeNode(input);
                node.setRightChild(rightNode);
            }
        }

        pre(findeNode(0));
        System.out.println("");
        in(findeNode(0));
        System.out.println("");
        post(findeNode(0));
        System.out.println("");

    }

    public static void pre(Node root) {
        System.out.print(root.getData()+" ");
        if(root.getLeftChild() != null) pre(root.getLeftChild());
        if(root.getRightChild() != null) pre(root.getRightChild());
    }

    public static void in(Node root) {

        if(root.getLeftChild() != null) in(root.getLeftChild());
        System.out.print(root.getData()+" ");
        if(root.getRightChild() != null) in(root.getRightChild());
    }

    public static void post(Node root) {

        if(root.getLeftChild() != null) post(root.getLeftChild());
        if(root.getRightChild() != null) post(root.getRightChild());
        System.out.print(root.getData()+" ");
    }

    public static Node findeNode(int key) {

        for(int i = 0 ; i < box.size() ; i++) {
            if(box.get(i).getData() == key) {
                return box.get(i);
            }
        }
        return new Node(key);
    }


}

class Node {
    private int data;
    private Node leftChild = null;
    private Node rightChild = null;

    public Node(int data) {
        this.data = data;
        Main.box.add(this);
    }

    public void setData(int data) {
        this.data = data;
    }

    public int getData() {
        return data;
    }

    public void setLeftChild(Node leftChild) {
        this.leftChild = leftChild;
    }

    public Node getLeftChild() {
        return leftChild;
    }

    public Node getRightChild() {
        return rightChild;
    }

    public void setRightChild(Node rightChild) {
        this.rightChild = rightChild;
    }
}