백준 1991 - 트리 순회

문제링크 : https://www.acmicpc.net/problem/1991

1991번: 트리 순회

 

Note

이 문제를 풀기위한  설명은 트리(Tree)와  이진트리(Binary Tree)  POST를 참고하면 된다.
첫 번째는 줄에는 노드의 개수이고 그 다음줄 부터 하나씩 읽어가면서 노드 , 왼쪽 자식노드, 오른쪽 자식노드 순으로 노드를 추가하면서 이진트리를 그성하고 pre-order, in-order, post-porder 순으로 순회하여 결과를 출력하면 된다.

 
import java.util.ArrayDeque;
import java.util.Queue;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.function.Consumer;
 
 
public class Main {
 
    public static class BTree<T extends Comparable<T>> {
 
        public Node root;
 
        public static class Node<T extends Comparable<T>> {
            public T data  ; // 노드의 값.
            public Node<T> parent  ; // 부모 노드를 가리킨다.
            public Node<T> left ; // 왼쪽 자식노드 (left child node)
            public Node<T> right  ; // 오른쪽 자식노드(right child node)
 
            Node(T data) {
                this.data = data;
            }
 
            public Node(Node<T> parent, T data ) {
                this.data = data;
                this.parent = parent;
                this.left = null;
                this.right = null;
            }
        }
 
        public Node addLeft(Node parent, T data) {
            Node node = new Node(parent, data);
            parent.left = node;
            return node;
        }
 
        public Node addRight(Node parent, T data) {
            Node node = new Node(parent, data);
            parent.right = node;
            return node;
        }
 
        public Node search(T data) {
            // level order 로 찾는다.
 
            if(root == null) {
                return null;
            }
 
            final Queue<Node> queue = new ArrayDeque<>();
            queue.add(root);
 
            while(!queue.isEmpty()) {
                Node node = queue.poll();
                if(node.data.compareTo(data) == 0) {
                    return node;
                }
                if(node.left != null) queue.add(node.left);
                if(node.right != null) queue.add(node.right);
            }
            return null;
        }
 
        public void preorderTraversal(Node node, Consumer<Node> consumer) {
            if(node == null)
                return;
 
            if(consumer != null) consumer.accept(node);
            preorderTraversal(node.left, consumer);
            preorderTraversal(node.right, consumer);
        }
 
        public void inorderTraversal(Node node, Consumer<Node> consumer) {
            if(node == null)
                return;
 
            // left -> root -> right
            inorderTraversal(node.left, consumer);
            if(consumer != null) consumer.accept(node);
            inorderTraversal(node.right, consumer);
        }
 
        public void postorderTraversal(Node node, Consumer<Node> consumer) {
            if(node == null)
                return;
 
            // left -> right -> root
            postorderTraversal(node.left, consumer);
            postorderTraversal(node.right, consumer);
            if(consumer != null) consumer.accept(node);
 
        }
 
    }
 
 
    public static void main(String[] args) throws IOException {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        BTree btree = new BTree();
 
        for(int i = 0 ; i < N ; i++) {
            String[] nodes = br.readLine().split(" ");
 
            BTree.Node node = btree.root == null ?
                    btree.root = new BTree.Node(nodes[0]) :
                    btree.search(nodes[0]) ;
 
            if(!nodes[1].equals(".")) btree.addLeft(node, nodes[1]);
            if(!nodes[2].equals(".")) btree.addRight(node, nodes[2]);
        }
 
 
        StringBuilder builder = new StringBuilder();
 
        btree.preorderTraversal(btree.root, new Consumer<BTree.Node>() {
            @Override
            public void accept(BTree.Node node) {
                builder.append(node.data);
            }
        });
        builder.append("\n");
 
        btree.inorderTraversal(btree.root, new Consumer<BTree.Node>() {
            @Override
            public void accept(BTree.Node node) {
                builder.append(node.data);
            }
        });
        builder.append("\n");
 
        btree.postorderTraversal(btree.root, new Consumer<BTree.Node>() {
            @Override
            public void accept(BTree.Node node) {
                builder.append(node.data);
            }
        });
        builder.append("\n");
 
        System.out.println(builder.toString());
    }
 
}