트리 순회(BFS, DFS)

📌 트리 순회 (Tree Traversal)

연결 리스트를 순회하는 방법은 선형 접근법 한 가지만 존재하지만, 트리 순회에는 다양한 접근법이 있다.
그 중 가장 널리 쓰이는 두 가지 접근법은 너비 우선 탐색 와 깊이 우선 탐색 이다.

1. BFS(Breadth First Search) : 너비 우선 탐색

자식 노드를 탐색하기 전에 형제 노드를 먼저 탐색한다.(수평적으로 탐색)

큐 (혹은 배열)를 만들어 수평으로 탐색한 값을 임시로 저장한다.
다른 배열을 하나 만들어 큐에 있는 값을 순서대로 전부 저장한다.

1. 큐에 root 먼저 담기
2. 큐에 담긴게 있을 때, 큐의 맨 앞 요소를 제거하고 다른 배열(data) 에 담기.
3. 제거한 값의 좌/우 값이 있을 경우 큐에 담기 (2,3 과정 반복)
4. 값이 탐색 순서대로 모두 담긴 data를 return

class Node {
    constructor(value){
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

class BinarySearchTree {
    constructor(){
        this.root = null;
    }
    insert(value){
        var newNode = new Node(value);
        if(this.root === null){
            this.root = newNode;
            return this;
        }
        var current = this.root;
        while(true){
            if(value === current.value) return undefined;
            if(value < current.value){
                if(current.left === null){
                    current.left = newNode;
                    return this;
                }
                current = current.left;
            } else {
                if(current.right === null){
                    current.right = newNode;
                    return this;
                } 
                current = current.right;
            }
        }
    }
    BFS(){
        var node = this.root,
            data = [],
            queue = [];
        queue.push(node); // root 담기

        while(queue.length){
           node = queue.shift();
           data.push(node.value);
           if(node.left) queue.push(node.left);
           if(node.right) queue.push(node.right);
        }
        return data;
    }
}


var tree = new BinarySearchTree();
tree.insert(10);
tree.insert(6);
tree.insert(15);
tree.insert(3);
tree.insert(8);
tree.insert(20);

// 		 10
//	  6		15
//  3  8	 20
tree.BFS(); // [10,6,15,3,8,20]

2. DFS(Depth First Search) : 깊이 우선 탐색

재귀를 사용한다. 크게 세 종류가 있다.

1) 전위 순회(PreOrder) : root -> left -> right

2) 중위 순회(InOrder) : left -> root -> right

3) 후위 순회(PostOrder) : left -> right -> root

class Node {
    constructor(value){
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

class BinarySearchTree {
    constructor(){
        this.root = null;
    }
    insert(value){
        var newNode = new Node(value);
        if(this.root === null){
            this.root = newNode;
            return this;
        }
        var current = this.root;
        while(true){
            if(value === current.value) return undefined;
            if(value < current.value){
                if(current.left === null){
                    current.left = newNode;
                    return this;
                }
                current = current.left;
            } else {
                if(current.right === null){
                    current.right = newNode;
                    return this;
                } 
                current = current.right;
            }
        }
    }
    DFSPreOrder(){
        var data = [];
        function traverse(node){
            data.push(node.value); // root 먼저 담기
            if(node.left) traverse(node.left); // 그 다음 left 재귀적으로 탐색
            if(node.right) traverse(node.right); // left가 없을 경우 right 재귀적으로 탐색
        }
        traverse(this.root);
        return data;
    }
    DFSPostOrder(){
        var data = [];
        function traverse(node){
            if(node.left) traverse(node.left); // 먼저 left 재귀적으로 탐색
            if(node.right) traverse(node.right); // 그 다음 rigth 재귀적으로 탐색
            data.push(node.value); // 마지막으로 root 담기
        }
        traverse(this.root);
        return data;
    }
    DFSInOrder(){
        var data = [];
        function traverse(node){
            if(node.left) traverse(node.left); // left 먼저 재귀적으로 탐색
            data.push(node.value); // root 담기
            if(node.right) traverse(node.right); // right 재귀적으로 탐색
        }
        traverse(this.root);
        return data;
    }
}


var tree = new BinarySearchTree();
tree.insert(10);
tree.insert(6);
tree.insert(15);
tree.insert(3);
tree.insert(8);
tree.insert(20);

// 		 10
//	  6		15
//  3  8	 20

tree.DFSPreOrder(); // [10,6,3,8,15,20]
tree.DFSPostOrder(); // [3,8,6,20,15,10]
tree.DFSInOrder(); // [3,6,8,10,15,20]

📌 BFS & DFS 비교

BFS와 DFS 중 어떤 것을 사용하는 것이 더 좋은가?

트리 모양에 따라 어떤 것을 써야 하는지가 달라진다.

ex. 깊이 보다 너비가 넓은 트리 : 깊이 우선 탐색이 공간 복잡도가 더 낫다.(시간 복잡도는 동일하다.)
너비 보다 깊이가 넓은 트리 : 너비 우선 탐색이 공간 복잡도가 더 낫다.(시간 복잡도는 동일하다.)

DFS의 세 가지 접근법 중 어떤 것을 선택해야 하는가?

• 전위 순회 : 트리를 복사하거나 평탄화 해서 저장하는 경우 (데이터 베이스에 저장했다가 나중에 연쇄 구조로 다시 만들어 낼 때) 도움된다.
• 중위 순회 : 이진 탐색 트리(BST)에 중위 순회를 적용하면 모든 노드가 순서대로 나오게 된다. (순서대로 작업하는 경우 유용하다.)