[JAVA] 이진트리에서 DFS 구현하기

이진트리란?

이진트리에서 DFS를 구현하는 포스트를 작성하기 앞서서 이진트리를 짚고 넘어가야 할 것 같다.

이진트리는 아주 중요한 트리구조이다.

 

이진트리는 모든 노드가 정확하게 두개의 서브트리를 가지고 있는 트리이다.

왼쪽서브트리와, 오른쪽 서브트리가 자식노드로 존재할 수 있다. 물론, 공백이 될 수도 있다.

 

 

출처:위키피디아

자식 노드 좌측은 부모노드보다 작은값, 우측은 큰 값으로   구성한다.

 

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

Node를 구현한 클래스이다. 데이터를 정수라고 두었다.

lt,rt는 각각 좌측,우측 자식노드를 구현한 것으로, 생성시에 자동으로 null값이 들어가도록 하였다.

 

---

DFS란?

 

DFS란, 트리나 그래프에서 한 루트로 탐색하다가 특정 상황에서 최대한 깊숙이 들어가서 확인한 뒤 다시 돌아가 다른 루트로 탐색하는 방식이다. 스택 배열로 구현하는 방법도 있지만, 우리는 재귀호출을 사용하여 구현해볼 것이다. 

 

단순 검색 속도 자체는 이후에 포스팅할 BFS에 비해서 느리다. 하지만 목적이 검색이 아닌 순회일 경우에는 많이 쓰인다. 특히 이진트리에서는 항상 순서대로 데이터를 방문한다는 장점이 있다.

 

저장공간의 수요가 비교적 적다는 장점이 있지만, 그래프의 경우, 해가 없는 경로에 깊이 빠질 가능성이 있고, 답이 다수인 문제에 대해 하나의 해에 다다르면 탐색을 끝내버리므로, 얻어진 해가 최단 경로가 된다는 보장이 없다.

 

 

이진트리에서의 DFS

이진트리에서 DFS 순회에는 부모노드순서를 기준으로 구분한 전위,중위,후위 순회가 있다.

부모노드와 자식노드 두개를 순회할 때, 부모노드순서를 기준으로 한다는 말은

부모노드를 먼저 방문하면 전위순회, 중간에 방문하면 중위 순회, 마지막에 방문하면 후위순회다.

 

내가 그린 트리 헤헤

 

 

 

위 이진트리에서 3가지 순회를 알아보겠다.

• 전위 순회 : 부모 - 왼쪽 - 오른쪽 ( 1 - 2 - 4 - 5 - 3 - 6 - 7)
• 중위 순회 : 왼쪽 - 부모 - 오른쪽 ( 4 - 2 - 5- 1 - 6 - 3 - 7) 
• 후위 순회 : 왼쪽 - 오른쪽 - 부모 ( 4 - 5 - 2 - 6 - 7 - 3 - 1)

 

JAVA로 DFS 구현하기

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

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

static Node root;
    public static void DFS(Node root){ //Postorder traversal(후위 순회)
        if(root==null) return;
        else{
            DFS(root.lt);
            DFS(root.rt);
            System.out.print(root.data+" ");
        }
    }

각각 전위,중위,후위 순회를 JAVA에서 구현한 것이다.

재귀를 이용하였는데 재귀가 스택형태를 이용한다는 것을 생각하면 생각보다 간단한것이다.

부모노드의 데이터를 뽑아내는 코드의 순서가 곧 방문한다는 것과 같다.

그 코드의 순서가 맨 앞에있으면 전위, 중간이면 중위, 마지막이면 후위 순회이다.