알고리즘) 트리 순회(백준 1991번)

 트리 순회에는 세 가지 방식이 있다. 각 방식의 차이는 부모 노드와 왼편 자식 노드, 오른편 자식 노드 이 셋의 순서에 있다. 특히나 부모 노드의 순서에 중점을 두는 것이 좋다. 선위 순회는 세 노드 중 부모 노드를 선두로 출력하고 중위 순회는 부모 노드를 중간 순서로, 후위 순회는 부모 노드를 마지막 순서로 출력한다.

작성 코드

package Tree;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

// 트리 순회
public class Algorithm1991 {
    Node header;

    static class Node {
        String data;
        Node lt, rt;

        public Node(String data) {
            this.data = data;
            lt = null;
            rt = null;
        }
    }

    Node findByData(String data) {
        Node root = this.header;
        if (root.data == data) return root;
        Queue<Node> q = new LinkedList<>();
        q.offer(root);

        while (!q.isEmpty()) {
            Node n = q.poll();
            if (n.lt != null) {
                if (n.lt.data.equals(data)) return n.lt;
                q.offer(n.lt);
            }
            if (n.rt != null) {
                if (n.rt.data.equals(data)) return n.rt;
                q.offer(n.rt);
            }
        }
        return null;
    }

    void preorderTraversalR(Node root) {
        if (root != null) {
            System.out.print(root.data);
            if (root.lt != null) preorderTraversalR(root.lt);
            if (root.rt != null) preorderTraversalR(root.rt);
        }
    }

    // 중위 순회(왼 -> 부모 -> 오)
    void inorderTraversalR(Node root) {
        if (root != null) {
            if (root.lt != null) inorderTraversalR(root.lt);
            System.out.print(root.data);
            if (root.rt != null) inorderTraversalR(root.rt);
        }
    }

    // 후위 순회(왼 -> 오 -> 부모)
    void postorderTraversalR(Node root) {
        if (root != null) {
            if (root.lt != null) postorderTraversalR(root.lt);
            if (root.rt != null) postorderTraversalR(root.rt);
            System.out.print(root.data);
        }
    }

    // bfs로 해결(Queue 사용)
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        Algorithm1991 tree = new Algorithm1991();
        int num = sc.nextInt();
        sc.nextLine();
        for (int i = 0; i < num; i++) {
            String line = sc.nextLine();
            String[] list = line.split(" ");

            if (i == 0) {
                tree.header = new Node(list[0]);
                if (!list[1].equals(".")) tree.header.lt = new Node(list[1]);
                if (!list[2].equals(".")) tree.header.rt = new Node(list[2]);
                continue;
            }

            Node p = tree.findByData(list[0]);
            if (!list[1].equals(".")) p.lt = new Node(list[1]);
            if (!list[2].equals(".")) p.rt = new Node(list[2]);
        }

        tree.preorderTraversalR(tree.header);
        System.out.println();

        tree.inorderTraversalR(tree.header);
        System.out.println();

        tree.postorderTraversalR(tree.header);
        System.out.println();
    }
}