트리 Tree - 02

이진 트리 순회

이진 트리를 순회하는 방법에는 선순위, 중순위, 후순위 3가지 방법이 있습니다.

이는 루트와 왼쪽 서브 트리, 오른쪽 서브 트리 중에서 루트를 언제 방문하느냐로 구분합니다.

---

선순위 순회 PreOrder Traversal

루트 -> 왼쪽 서브 트리 -> 오른쪽 서브 트리 순서로 방문합니다.

traversePreOrder(node = this.root, result = []) {
  if (node) {
    result.push(node.value);

    this.traversePreOrder(node.left, result);
    this.traversePreOrder(node.right, result);
  }

  return result;

}

---

중순위 순회 InOrder Traversal

왼쪽 서브 트리 -> 루트 -> 오른쪽 서브 트리를 순서로 방문합니다.

traverseInOrder(node = this.root, result = []) {
  if (node) {
    this.traverseInOrder(node.left, result);

    result.push(node.value);

    this.traverseInOrder(node.right, result);
  }

  return result;
}

---

후순위 순회 PostOrder Traversal

왼쪽 서브 트리 -> 오른쪽 서브 트리 -> 루트를 순서로 방문합니다.

traversePostOrder(node = this.root, result = []) {
  if (node) {
    this.traversePostOrder(node.left, result);
    this.traversePostOrder(node.right, result);

    result.push(node.value);

  }

  return result;
}

---

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

너비 우선 탐색은 인접한 노드(같은 레벨)들을 먼저 탐색하는 방식입니다.

너비 우선 탐색은 루트를 방문한 후 시작점에서 가까운 모든 노드들을 우선 방문하는 탐색 알고리즘입니다.

---

구현 코드

큐를 이용해서 구현

출발점을 먼저 큐에 넣고, 큐가 빌 때까지 아래 과정을 반복합니다.

1. 큐에 저장된 노드를 하나 Dequeue합니다.
2. Dequeue한 정점과 연결된 모든 노드를 큐에 추가합니다.

// 이진 트리에서 BFS
bfs() {
    if (!this.root) return;

    let queue = [];
    let result = [];

    queue.push(this.root);

    while (queue.length) {
      let curNode = queue.shift();

      result.push(curNode);

      // 현재 부모 노드의 자식들을 모두 다 큐에 담는다.
      if (curNode.left) queue.push(curNode.left);
      if (curNode.right) queue.push(curNode.right);
    }

    return result;
  }

출발 노드에서 목표 노드까지의 최단 길이 경로를 보장합니다.

경로가 길 경우 탐색 수가 증가함에따라 큐에 메모리를 많이 사용하게 됩니다.

---

깊이 우선 탐색 DFS (Depth first Search)

깊이 우선 탐색은 자식 노드(같은 레벨)들을 먼저 탐색하는 방식입니다.

깊이 우선 탐색은 루트를 방문한 후 시작점에서 갈 수 있는 정점부터 깊이 있게 파고드는 탐색 알고리즘입니다.

---

구현 코드

스택 또는 재귀함수로 구현

// 이진 트리에서 DFS
dfs(node = this.root, result = []) {
    if (!node) return;

    result.push(node);

    if (node.left) this.dfs(node.left, result);
    if (node.right) this.dfs(node.right, result);

    return result;
  }

---

비교

• 경로의 특징

  각 정점에 숫자가 적혀있고 a부터 b까지 가는 경로를 구하는데 경로에 같은 숫자가 있으면 안 된다는 문제 등, 각각의 경로마다 특징을 저장해둬야 할 때는 DFS를 사용합니다.

  BFS는 경로의 특징을 가지지 못합니다.

• 최단거리

  미로 찾기 등 최단거리를 구해야 할 경우, BFS가 유리합니다.

  너비 우선 탐색으로 현재 노드에서 가까운 곳부터 찾기 때문에 경로를 탐색 시 먼저 찾아지는 해답이 곧 최단거리입니다.

• 대상 규모

  검색 대상의 규모가 클 경우 DFS를 작을 경우 BFS를 먼저 고려해보자.