이진트리탐색 (DFS)

깊이 우선 탐색의 방법에는

전위탐색, 중위탐색, 후위탐색이 있다.

1. 전위탐색 : 자신 node를 먼저 탐색한 뒤 왼쪽 자식이 있으면 왼쪽 자식 node를 깊이 파고들고, 없으면 그 다음 오른쪽 자식 node탐색
2. 중위탐색 : 왼쪽자식 -> 자신 -> 오른쪽 자식
3. 후위탐색 : 왼쪽자식 -> 오른쪽 자식 -> 자신

        1
   2        3
4   5    6   7
와 같은 구조의 이진트리가 있을 때

전위탐색 : 1 2 4 5 3 6 7
중위탐색 : 4 2 5 1 6 3 7
후위탐색 : 4 5 2 6 7 3 1

와 같은 결과가 나와야 한다.
이를 코드로 구현하면

public class Main {

    static Tree root;

    public static void main(String[] args) {
        nodeSetting();
        
        System.out.print("전위탐색 시작 : ");
        beforeSearch(root);
        System.out.println();
        
        System.out.print("중위탐색 시작 : ");
        middleSearch(root);
        System.out.println();
        
        System.out.print("후위탐색 시작 : ");
        afterSearch(root);
    }

    //전위탐색
    public static void beforeSearch(Tree node){
        System.out.print(node.data+" ");
        if(node.ln != null) beforeSearch(node.ln);
        if(node.rn != null) beforeSearch(node.rn);
    }

    //중위탐색
    public static void middleSearch(Tree node){
        if(node.ln != null) middleSearch(node.ln);
        System.out.print(node.data+" ");
        if(node.rn != null) middleSearch(node.rn);
    }

    //후위탐색
    public static void afterSearch(Tree node){
        if(node.ln != null) afterSearch(node.ln);
        if(node.rn != null) afterSearch(node.rn);
        System.out.print(node.data+" ");
    }

    public static class Tree{
        int data;
        Tree ln = null;
        Tree rn = null;

        public Tree(int data){
            this.data = data;
        }
    }

    public static void nodeSetting(){
        root = new Tree(1);
        root.ln = new Tree(2);
        root.rn = new Tree(3);
        root.ln.ln = new Tree(4);
        root.ln.rn = new Tree(5);
        root.rn.ln = new Tree(6);
        root.rn.rn = new Tree(7);
    }
}

와 같이 나타낼 수 있다.

전위탐색 시작 : 1 2 4 5 3 6 7 
중위탐색 시작 : 4 2 5 1 6 3 7 
후위탐색 시작 : 4 5 2 6 7 3 1