백준 : 트리 순회 #1991 [JAVA]

트리 순회 #1991

문제 원본 링크

개인 노션 링크

[문제 설명]

이진 트리를 입력받아 순회 종류에 따라 결과를 출력하는 프로그램을 작성하시오.

• 전위 순회(preorder traversal)
• 중위 순회(inorder traversal)
• 후위 순회(postorder traversal)

입력 조건

1. 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다.

2. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다.

3. 노드의 이름은 A부터 차례대로 알파벳 대문자로 매겨지며, 항상 A가 루트 노드가 된다.

4. 자식 노드가 없는 경우에는 . 으로 표현한다.

풀이 과정

• 트리에 저장될 노드 클래스
  • 노드에 저장될 data와 자식 노드들을 필드로 가진다.

class Node {
    private char data;
    private Node leftNode;
    private Node rightNode;

    char getData() {
        return this.data;
    }

    Node getLeftNode() {
        return this.leftNode;
    }

    Node getRightNode() {
        return this.rightNode;
    }

    void setLeftNode(Node node) {
        this.leftNode = node;
    }

    void setRightNode(Node node) {
        this.rightNode = node;
    }

    Node(char data) {
        this.data = data;
    }
}

• 트리를 구성하는 트리 클래스
  • 기본적으로 root 노드를 갖도록 하였다.
  • 루트 노드를 생성하는 createNode( ) 메소드
  • 루트 노드가 아닌 노드를 생성하는 recursiveNode( ) 메소드
  • 전위, 중위, 후위 순회를 동작하는 메소드들
    • preOrderTraversal( )
    • inOrderTraversal( )
    • postOrderTraversal( )

class Tree {
    public Node root;

    public void createNode(char data, char left, char right) {
        if (root == null) { //맨 처음 루트노드 생성 코드
            root = new Node(data);
            if (left == '.') {
                root.setLeftNode(null);
            } else {
                root.setLeftNode(new Node(left));
            }

            if (right == '.') {
                root.setRightNode(null);
            } else {
                root.setRightNode(new Node(right));
            }

        } else {
            recursiveNode(root, data, left, right); //루트가 있다면 재귀 방식으로 해당 위치 이동
        }
    }

    public void recursiveNode(Node node, char data, char left, char right) {
        if (node == null) { //말단일 경우 여기로 들어와서 return됨
            return;
        } else if (node.getData() == data) {
            if (left == '.') {
                node.setLeftNode(null);
            } else {
                node.setLeftNode(new Node(left));
            }

            if (right == '.') {
                node.setRightNode(null);
            } else {
                node.setRightNode(new Node(right));
            }
        } else { //해당 위치로 이동할 때까지 재귀 호출
            recursiveNode(node.getLeftNode(), data, left, right);
            recursiveNode(node.getRightNode(), data, left, right);
        }
    }

    public void preOrderTraversal(Node node) {
        if (node != null) {
            System.out.print(node.getData());
            if (node.getLeftNode() != null) preOrderTraversal(node.getLeftNode());
            if (node.getRightNode() != null) preOrderTraversal(node.getRightNode());
        }
    }

    public void inOrderTraversal(Node node) {
        if (node != null) {
            if (node.getLeftNode() != null) inOrderTraversal(node.getLeftNode());
            System.out.print(node.getData());
            if (node.getRightNode() != null) inOrderTraversal(node.getRightNode());
        }
    }

    public void postOrderTraversal(Node node) {
        if (node != null) {
            if (node.getLeftNode() != null) postOrderTraversal(node.getLeftNode());
            if (node.getRightNode() != null) postOrderTraversal(node.getRightNode());
            System.out.print(node.getData());
        }
    }
}

• main 메소드를 가진 구동 클래스
  • BufferedReader를 통해 사용자의 입력값을 받는다.
  • StringTokenizer를 이용해 입력값을 구분한다.

public class Main {
    public static BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        Tree tree = new Tree();

        System.out.print("생성할 노드 갯수를 입력하세요 > ");
        int nodeCount = Integer.parseInt(String.valueOf(bufferedReader.readLine()));

        for (int i = 0; i < nodeCount; i++) {
            System.out.print((i + 1) + "번째 노드 이름, 왼쪽 자식 노드, 오른쪽 자식 노드를 순서대로 입력하세요 > ");
            String str = bufferedReader.readLine();

            StringTokenizer st = new StringTokenizer(str, " ", false);
            char root = st.nextToken().charAt(0);
            char lNode = st.nextToken().charAt(0);
            char rNode = st.nextToken().charAt(0);

            tree.createNode(root, lNode, rNode);
        }

        tree.preOrderTraversal(tree.root);
        System.out.println();

        tree.inOrderTraversal(tree.root);
        System.out.println();

        tree.postOrderTraversal(tree.root);
    }
}