[자료구조] 너비 우선 탐색(BFS), 깊이 우선 탐색(DFS)

1. 너비 우선 탐색(Breadth-first-Search)[BFS]

너비우선 탐색은 트리를 가로질러서 순회한다.

예시) 루트 -> 루트의 자식들 -> 루트의 자식들의 자식들

아래로 내려가기전에 같은 레벨에 있는 모든 노드들을 거쳐가는것이고 큐를 이용한다.

2. 깊이 우선 탐색(Depth-first-Search)[DFS]

형제 노드로 넘어가기전에 수직으로 트리의 끝까지 내려간다.

(1) 전위 탐색 : 왼쪽을 모두 순회한 다음 오른쪽 순회

(2) 후위 탐색 : 루트가 가장 마지막에 순회한다 -> 거꾸로 순회한다.

(3) 중위 탐색 : 먼저 왼쪽 전체를 순회하고 노드를 방문하고 그다음 오른쪽 순회

3. 너비우선과 깊이우선 사용

시간 복잡도는 둘다 같지만 트리에 따라 공간복잡도가 다르다.

완전히 펼쳐져서 넓게 펴진 상태로 아래까지 뻗어나가는 트리를 작업할때 너비 우선 탐색을 사용한다면 모든 노드를 저장하기 위해 큐를 사용한다.

깊이보다 너비가 넓은 트리의 경우에는 깊이 우선 탐색이 더 적은 공간을 점유한다.

깊이가 매우 길다면 너비 우선이 더 낫다.

4. 전위 후위 중위 사용

이진트리를 순회하는 경우 전위 탐색을 하면 오름차순으로 정리된다.

트리를 복사하거나 평탄화해서 저장하는 경우 나중에 연쇄구조로 다시 만들어 낼때 전위탐색이 도움이 된다.

전위 : 루트를 바로 알수 있다.

5. BFS

[자료구조] 이진트리

이진트리에 이어서 메소드 작성

BFS() {
    let data = [];
    let queue = [];
    let node = this.root;
    queue.push(node);
    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;
  }

6. DFS

(1) 전위

DFSPreOrder() {
    let data = [];
    function traverse(node) {
      data.push(node.value);
      if (node.left) traverse(node.left);
      if (node.right) traverse(node.right);
    }
    traverse(this.root);
    return data;
}

(2) 후위

 DFSPostOrder() {
    let data = [];
    function traverse(node) {
      if (node.left) traverse(node.left);
      if (node.right) traverse(node.right);
      data.push(node.value);
    }
    traverse(this.root);
    return data;
  }

(3) 중위

DFSInOrder() {
    let data = [];
    function traverse(node) {
      node.left && traverse(node.left);
      data.push(node.value);
      node.right && traverse(node.right);
    }
    traverse(this.root);
    return data;
}