// 이진트리 클래스
class Node {
    int data;
    Node lt, rt;
    public Node(int val) {
        data = val;
        lt = rt = null;
    }
}
public class Binary_Tree_Traversal_DFS {

    static Node root;
    
    // 전위
    public static void DFS1(Node root) {
        if ( root == null ) return;
        else {
            System.out.print(root.data + " ");
            DFS1(root.lt);
            DFS1(root.rt);
        }
    }

    // 중위
    public static void DFS2(Node root) {
        if ( root == null ) return;
        else {
            DFS2(root.lt);
            System.out.print(root.data + " ");
            DFS2(root.rt);
        }
    }

    // 후위
    public static void DFS3(Node root) {
        if ( root == null ) return;
        else {
            DFS3(root.lt);
            DFS3(root.rt);
            System.out.print(root.data + " ");
        }
    }
	
    public static void main(String[] args) {
        root = new Node(1);
        root.lt = new Node(2);
        root.rt = new Node(3);
        root.lt.lt = new Node(4);
        root.lt.rt = new Node(5);
        root.rt.lt = new Node(6);
        root.rt.rt = new Node(7);

        System.out.println("전위");
        DFS1(root);

        System.out.println("\n");
        System.out.println("중위");
        DFS2(root);

        System.out.println("\n");
        System.out.println("후위");
        DFS3(root);

    }


}