이진 트리 순회

트리순회 결과 출력하기 (tree.cpp)

 

문제

---

이진 트리를 입력받아 전위순회, 중위순회, 후위순회 결과를 출력하는 프로그램을 작성하시오.

 

입력

---

첫째 줄에 노드의 개수 N이 주어진다. 이어 N개의 줄에는 트리의 연결 상황이 주어지는데 아래의 예와 같은 형식으로 각 줄에 그 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 매겨지며 항상 A가 루트 노드가 된다. 만약 특정 노드 사이의 자식이 하나이거나 없을 경우 자식 노드 대신 ‘.’이 주어진다. N은 26 이하의 자연수이다.

 

출력

---

첫째 줄에 전위순회 한 결과를, 둘째 줄에 중위순회 한 결과를, 셋째 줄에는 후위순회 한 결과를 출력한다.

 

예제 입력

7
A B C
B D .
C E F
E . .
F . G
D . .
G . .

예제 출력

ABDCEFG
DBAECFG
DBEGFCA




코드

//트리순회

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;
        char input;

        a = sc.nextInt();

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

            input = sc.next().charAt(0);
            if(input != '.') {
                leftNode = findeNode(input);
                node.setLeftChild(leftNode);
            }

            input = sc.next().charAt(0);
            if(input != '.') {
                rightNode = findeNode(input);
                node.setRightChild(rightNode);
            }
        }

        pre(findeNode('A'));
        System.out.println("");
        in(findeNode('A'));
        System.out.println("");
        post(findeNode('A'));
        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(char 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 char data;
    private Node leftChild = null;
    private Node rightChild = null;

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

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

    public char 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;
    }
}