DFS - 전위 순회, 중위 순회, 후위 순회

DFS 란?

• 그래프를 탐색하는 알고리즘.
• 하나의 경로를 끝까지 탐색한 후, 다음 경로를 탐색하는, 깊이 우선 탐색 (Depth-First Search)
• BFS 보다 탐색 시간은 조금 오래 걸리나, 모든 노드를 완전히 탐색할 수 있다. 
  • BFS 로 탐색할 경우 첫 번째에 해당하는 경로가 원하는 목적지라 하더라도 다른 모든 경로를 살펴보아야 한다. 

 

전위 순회, 중위 순회, 후위 순회

트리를 순회하는 3가지 방법으로 전위 순회, 중위 순회, 후위 순회가 있다. 

 

DFS 는 재귀를 통해 순회가 이루어저는데,

맨 처음 지정 노드에 대해 호출되면, 해당 노드의 자식 노드가 존재하면 자식 노드에 대해 재귀 호출하고,

그 자식 노드의 자식 노드가 존재하면 자식의 자식 노드에 대해 또 다시 재귀 호출한다.

더이상 자식 노드가 없어서 호출된 노드가 null 이 되면 재귀 호출이 멈추고 전단계로 돌아가 다음 자식을 탐색하는 것이다. 

 

이 때, 값에 대한 확인이나 출력 혹은 리스트에 저장하는 등의 행위를 왼쪽, 오른쪽 자식 노드에 대한 재귀 호출과 순서를 어떻게 하느냐에 따라 전위 순회, 중위 순회, 후위 순회로 나누어진다. 

부모 노드를 탐색하는 순서와도 같다. 

 

1. 전위 순회 : 부모 노드 -> 왼쪽 자식 노드 -> 오른쪽 자식 노드 의 순서로 순회하는 방법
2. 중위 순회 : 왼쪽 자식 노드 -> 부모 노드 -> 오른쪽  자식 노드 의 순서로 순회하는 방법
3. 후위 순회 : 왼쪽 자식 노드 -> 오른쪽 자식 노드 -> 부모 노드 의 순서로 순회하는 방법

 

 

import java.util.*;

class Node { // 트리를 이루는 노드
    int data;
    Node lt, rt;

    public Node(int data) {
        this.data = data;
        lt = rt = null;
    }
}

public class Test {
    public static ArrayList<Integer> preDFS(Node root, ArrayList<Integer> list) { // 전위 순회
        if(root != null) {
            list.add(root.data);
            preDFS(root.lt, list);
            preDFS(root.rt, list);
        }

        return list;
    }
    public static ArrayList<Integer> inDFS(Node root, ArrayList<Integer> list) { // 중위 순회
        if(root != null) {
            inDFS(root.lt, list);
            list.add(root.data);
            inDFS(root.rt, list);
        }

        return list;
    }
    public static ArrayList<Integer> postDFS(Node root, ArrayList<Integer> list) { // 후위 순회
        if(root != null) {
            postDFS(root.lt, list);
            postDFS(root.rt, list);
            list.add(root.data);
        }

        return list;
    }

    public static void main(String[] args) {
        Node 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);

        ArrayList<Integer> preList = preDFS(root, new ArrayList<>());
        System.out.println(preList.toString()); // [1, 2, 4, 5, 3, 6, 7]

        ArrayList<Integer> inList = inDFS(root, new ArrayList<>());
        System.out.println(inList.toString()); // [4, 2, 5, 1, 6, 3, 7]

        ArrayList<Integer> postList = postDFS(root, new ArrayList<>());
        System.out.println(postList.toString()); // [4, 5, 2, 6, 7, 3, 1]
    }
}