[재귀함수] 재귀함수 기초 - 3

재귀함수 기초 문제들 해설 및 정리 

 

이진트리 순회는 전위순회 , 중위순회 , 후위순휘 종류가 있습니다.

 

 

1번을 root 라고 표현

 

전위는 1 2 4 5 3 6 7 위에 부터 왼쪽 -> 오른쪽 순으로 탐색하고

중위는 4 2 5 1 6 3 7 왼쪽 -> 오른쪽 탐색

후위순회는 4 5 2 6 7 3 1 순으로 탐색 

 

package TreeDFS;

import com.sun.tools.javac.Main;

// 1. Node 클래스를 만들어준다.
class Node{
    // 2. data로 받을값과 좌우를 탐색하기 위한 lt , rt를 Node 클래스 형태로 선언
    int data;
    Node lt, rt;
    public Node(int val){
        data = val;
        lt=rt=null;
    }
}

public class TreeDFS {
    // 3. Node 객체의 뿌리를 선언
    Node root;

    // 8. DFS 함수를 실행 시킴
    public void DFS(Node root){
        // 9. 마지막 노드까지 왔으면 null이기 때문에 종료
        if(root == null){
            return;
        } else {
            // 10. 다시 왼쪽의 루트를 호출해서 왼쪽부터 탐색하게 만들어 준다. 다시 DFS 호출 9번으로
            // System.out.print를 찍는 위치에 따라 전위,중위,후위가 나뉘어짐
            DFS(root.lt);
            DFS(root.rt);
        }
    }

    public static void main(String[] args) {
        // 4. tree 형태의 객체를 생성
        TreeDFS tree = new TreeDFS();
        // 5. tree의 root에 1이라는 Node 타입 생성 [ 이러면 lt , rt 는 null인 상태 ]
        tree.root = new Node(1);

        // 6. tree의 root의 lt,rt 값에 Node 타입을 생성해서 넣어줌 [ 이러면 lt,rt 객체 형태의 2,3 을 data 값을 가지게 됨 ]
        tree.root.lt = new Node(2);
        tree.root.rt = new Node(3);

        // 7. tree의 1번 노드 root노드 부터 시작
        tree.DFS(tree.root);

    }
}

System.out.print 위치는 직접 디버깅 해보면서 풀어보도록 하자!