[알고리즘] 이진트리탐색 구현하기 - DFS(깊이우선탐색)

이진트리탐색 구현하기- DFS(깊이우선탐색)

 

 

 

코드

• Node 클래스 생성
  • 각 node는 값, 왼쪽자식, 오른쪽자식으로 구성되어있음.
• 이진트리탐색(DFS)
  • 출력문의 위치에 따라 전위우선탐색, 중위우선탐색, 후위우선탐색으로 바뀔 수 있음.

 

class Node {
    int data;
    Node lt,rt;
    public Node(int val) {
        data = val;
        lt=rt=null;
     }
}

static Node root;
public static void DFS(Node root){
    if(root==null) return;
    else{
        System.out.print(root.data + " ");
        DFS(root.lt);
        DFS(root.rt);
    }
}
            
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);

    DFS(root); // 출력: 1 2 4 5 3 6 7 (전위우선탐색)
}

 

 

 

 

 

전위우선탐색

• 부모-왼쪽-오른쪽 순으로 방문

public static void DFS(Node root){
    if(root==null) return;
    else{
        System.out.print(root.data + " "); // 루트 노드 방문
        DFS(root.lt); // 왼쪽 자식 노드 탐색
        DFS(root.rt); // 오른쪽 자식 노드 탐색
    }
}

 

 

 

중위우선탐색

• 왼쪽-부모-오른쪽 순으로 방문

public static void DFS(Node root){
    if(root==null) return;
    else{
        DFS(root.lt); // 왼쪽 자식 탐색
        System.out.print(root.data + " "); // 루트 노드 방문
        DFS(root.rt); // 오른쪽 자식 탐색
    }
}

 

 

 

 

후위우선탐색

• 왼쪽-오른쪽-루트 순으로 방문

public static void DFS(Node root){
    if(root==null) return;
    else{
        DFS(root.lt); // 왼쪽 자식 탐색
        DFS(root.rt); // 오른쪽 자식 탐색
        System.out.print(root.data + " "); // 루트 노드 방문
    }
}