트리 순회 (BFS, DFS)

트리 순회란?

자료구조의 종류 중 하나인 트리 구조에서 가각의 노드를 한 번씩 방문하는 과정을 의미한다.
순회라는 방법은 노드를 방문하는 순서에 따라 분류되는데 너비 우선 탐색과 깊이 우선 탐색으로 분류할 수 있다.

너비 우선 탐색 (Breadth First Search)

같은 층에 있는 노드를 우선적으로 탐색한다.
10 -> 6 -> 15 -> 3 -> 8 -> 20

자료구조 중 하나인 queue를 이용하여 구현한다.

  BFS() {
    let node = this.root;
    const data = [];
    const queue = [];
    queue.push(node);

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

    return data;
  }

깊이 우선 탐색 (Depth First Search)

깊이에 따라 노드들을 탐색하는 방식이다.

전위순회, 중위순회, 후위순회 3가지의 방법이 있다.

전위 순회

루트 -> 왼쪽 자식 -> 오른쪽 자식 순으로 순회한다.

10 -> 6 -> 3 -> 8 -> 15 -> 20

  DFSPreOrder() { // 전위 순회
    const 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;
  }

중위 순회

왼쪽 자식 -> 루트 -> 오른쪽 자식 순으로 순회한다.

3 -> 6 -> 8 -> 10 -> 15 -> 20

  DFSInOrder() { // 중위 순회
    const data = [];
    function traverse(node) {
      if(node.left) traverse(node.left);
      data.push(node);
      if(node.right) traverse(node.right);
    }
    traverse(this.root);
    return data;
  }

후위 순회

왼쪽 자식 -> 오른쪽 자식 -> 루트 순으로 순회한다.

3 -> 8 -> 6 -> 20 -> 15 -> 10

  DFSPostOrder() { // 후위 순회
    const 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;
  }

BFS, DFS 모두 자식 노드들을 한 번씩 순회하기 때문에 시간복잡도는 동일하다.

하지만 공간 복잡도의 경우 너비가 넓은 트리의 경우 깊이 우선 탐색이 더 유리하고, 트리의 깊이가 깊을수록 너비 우선 탐색이 더 유리하다.