DFS와 BFS 와 이진트리순회

먼저 그래프 탐색(Graph Search)이란 하나의 정점으로부터 시작해 차례대로 모든 정점을 방문한다.

예시로는 도로망에서 특정 도시에서 다른 도시로갈 수 있는지 여부, 전자회로에서 특정 단자와 다른 단자가 서로 연결되어 있는지 여부가 있다.

대표적은 그래프 탐색 알고리즘에는 DFS/BFS가 있다.

 

DFS(Depth-First Search, 깊이 우선 탐색)

트리나 그래프에서 한 루프로 탐색하다가 특정 상황에서 최대한 깊숙이 들어가서 확인한 뒤, 다시 돌아가 다른 루트로 탐색하는 방식이다.

대표적으로 백트래킹에 사용된다.

일반적으로 재귀 호출을 사용해 구현하지만, 단순하게 스택 배열로 구현할 수도 있다.

 

(참고로 트리는 특정 조건을 만족하는 그래프이다. 즉 트리는 그래프이지만, 그래프는 트리가 아님!)

 

DFS로 이진트리 순회 풀기

이진트리(Binary Tree) : 트리의 일종으로 부모(root)를 기준으로 왼쪽자식, 오른쪽 자식이 존재하고, 모든 노드들의 자식 노드가 두개 이하인 트리를 의미한다.

 

이진트리에 해당하는 검색 알고리즘은 2가지가 DFS, BFS가 존재하는데 여기서는 DFS로 풀어보겠다.

 

 

만약 위와 같은 그림의 이진트리가 있다면, 

• 전위순회 (preorder traverse) 출력 : 부모 - 왼 - 오 순으로 방문, 1 2 4 5 3 6 7 순으로 출력되야한다.
• 중위순회(inorder traverse) 출력 : 왼 - 부모- 오 순으로 방문, 4 2 5 1 6 3 7 순으로 출력되야한다.
• 후위순위(postorder traverse) 출력 : 왼 - 오 - 부모 순으로 방문, 4 5 2 6 7 3 1 순으로 출력되야한다.

 

class Node {
    //데이터 값
    int data;
    //왼,  오 자식의 노 드주소
    //node 라는 클래스의 객체 주소를 저장
    Node lt, rt;

    //생성자
    public Node(int val) {
        data = val;
        lt = rt = null;
    }
}

public class BinaryTreeDFS {
    Node root;

    //7-5. 이진트리순회 (Depth-First Search) - 재귀를 활용
    public void DFS(Node root) {
        //DFSMain의 인스턴스 메서드
        if (root == null) {
            //맨 밑 노드
            return;
        } else {
            //전위순회 출력
            System.out.print(root.data + " ");
            DFS(root.lt);
            //중위순회 출력
            System.out.print(root.data + " ");
            DFS(root.rt);
            //후위순회 출력
            System.out.print(root.data + " ");
        }
    }

    public static void main(String[] args) {
        // DFSMain class 객체, 그리고 이 안의 객체안에 root라는 변수가 존재 (node라는 클래스의 객체 주소를 저장하고 있는 변수)
        BinaryTreeDFS tree = new BinaryTreeDFS();

        //이진 트리 만들기
        //new로 객체를 생성하고 생긴 주소값을 tree.root랑 연결
        tree.root = new Node(1);
        tree.root.lt = new Node(2);
        tree.root.rt = new Node(3);
        tree.root.lt.lt = new Node(4);
        tree.root.lt.rt = new Node(5);
        tree.root.rt.lt = new Node(6);
        tree.root.rt.rt = new Node(7);
        tree.DFS(tree.root);
    }
}

 

 

 

BFS (Breath-first Search , 너비 우선 탐색)

트리나 그래프에서 하나의 정점에서 시작해 인접한 모든 노드를 먼저 탐색하고, 멀리 떨어져 있는 정점을 나중에 방문하는 순회방법이다.

주로 두 노드 사이의 최단 경로를 찾고 싶을 때 이 방법을 선택한다.

그리고 BFS는 Queue라는 자료구조를 사용한다.

 

BFS로 이진트리 레벨 탐색



위와 똑같은 예시가 있다고 할때, 

• 레벨 순으로 순회  (Level order traversal) 출력 : 레벨 순으로 1 2 3 4 5 6 7 순으로 출력되야한다.

class Node {
    //데이터 값
    int data;
    //왼, 오 자식의 노드 주소
    Node lt, rt;

    //생성자
    public Node(int val) {
        data = val;
        lt = rt = null;
    }
}

public class BinaryTreeBFS {
    //7-7. 이진 트리 레벨 탐색 (Breadth-First Search)

    Node root;

    public void BFS(Node root) {

        //스택 생성
        Queue<Node> Q = new LinkedList<>();
        Q.offer(root);

        //레벨(몇번만에 그 거리를 가느냐)
        int L = 0;
        while (!Q.isEmpty()) {
            int len = Q.size();
            System.out.print(L + "  : ");
            for (int i = 0; i < len; i++) {
                Node cur = Q.poll();
                System.out.print(cur.data + " ");
                //출력하고 이 노드와 연결된 자식을 스택에  다시 넣기
                if (cur.lt != null) {
                    Q.offer(cur.lt);
                }
                if (cur.rt != null) {
                    Q.offer(cur.rt);
                }
            }
            //for문이 끝났다는 거는 하나의 레벨이 끝났다는 의미
            L++;
            System.out.println();

        }
    }
    //즉, 레벨 별로 for문을 돌면서 출력하고 출력한 값의 자식 노드를 다시 스택에 넣기

    public static void main(String[] args) {
        // BinaryTreeBFS class 객체, 그리고 이 안의 객체안에 root라는 변수가 존재
        BinaryTreeBFS tree = new BinaryTreeBFS();

        tree.root = new Node(1);
        tree.root.lt = new Node(2);
        tree.root.rt = new Node(3);
        tree.root.lt.lt = new Node(4);
        tree.root.lt.rt = new Node(5);
        tree.root.rt.lt = new Node(6);
        tree.root.rt.rt = new Node(7);

        tree.BFS(tree.root);


    }
}