DFS, BFS, 트리 순회(traversal)

이진트리에서 데이터를 검색하거나 방문하는 방법에는 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS), 그리고 트리 순회(Traversal)가 있습니다. 각각의 방법은 특정 목적에 따라 사용되며, 이진트리의 모든 노드를 효율적으로 방문하는 다양한 전략을 제공합니다.

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

DFS는 트리의 깊이를 우선적으로 탐색하는 알고리즘입니다. 트리의 루트에서 시작하여 가능한 한 깊게 트리를 탐색한 후, 더 이상 탐색할 노드가 없을 때 이전 분기점으로 되돌아가 다른 경로를 탐색합니다. 이진트리에서 DFS를 구현하는 세 가지 주요 방법은 전위 순회(Preorder), 중위 순회(Inorder), 후위 순회(Postorder)입니다.

• 전위 순회 (Preorder): 루트를 먼저 방문하고, 왼쪽 서브트리, 그리고 오른쪽 서브트리를 순서대로 방문합니다.
• 중위 순회 (Inorder): 왼쪽 서브트리를 먼저 방문한 후, 루트를 방문하고, 마지막으로 오른쪽 서브트리를 방문합니다. 이 방법은 이진 탐색 트리에서 정렬된 순서로 노드를 방문할 때 사용됩니다.
• 후위 순회 (Postorder): 왼쪽 서브트리, 오른쪽 서브트리를 먼저 방문하고, 마지막으로 루트를 방문합니다.

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

BFS는 트리의 각 레벨(level)에 있는 노드를 왼쪽에서 오른쪽으로 방문합니다. 이 방법은 큐(queue)를 사용하여 각 레벨의 모든 노드를 저장하고, 큐가 빌 때까지 노드를 차례대로 방문하며 처리합니다. BFS는 레벨 순회(Level Order Traversal)라고도 불립니다.

트리 순회 (Traversal) 예제

아래 코드는 이진트리의 DFS(전위, 중위, 후위 순회)와 BFS(레벨 순회)를 구현한 예제입니다.

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

class BinaryTree {
  constructor() {
    this.root = null;
  }

  // 전위 순회
  preorderTraversal(node = this.root) {
    if (node !== null) {
      console.log(node.data); // 루트 방문
      this.preorderTraversal(node.left); // 왼쪽 서브트리 순회
      this.preorderTraversal(node.right); // 오른쪽 서브트리 순회
    }
  }

  // 중위 순회
  inorderTraversal(node = this.root) {
    if (node !== null) {
      this.inorderTraversal(node.left); // 왼쪽 서브트리 순회
      console.log(node.data); // 루트 방문
      this.inorderTraversal(node.right); // 오른쪽 서브트리 순회
    }
  }

  // 후위 순회
  postorderTraversal(node = this.root) {
    if (node !== null) {
      this.postorderTraversal(node.left); // 왼쪽 서브트리 순회
      this.postorderTraversal(node.right); // 오른쪽 서브트리 순회
      console.log(node.data); // 루트 방문
    }
  }

  // BFS (레벨 순회)
  bfs() {
    let queue = [this.root];
    while (queue.length > 0) {
      let node = queue.shift(); // 큐의 첫 번째 노드를 제거하고 반환
      console.log(node.data);
      if (node.left !== null) queue.push(node.left);
      if (node.right !== null) queue.push(node.right);
    }
  }
}

이 예제는 이진트리의 기본적인 순회 방법을 보여줍니다. 각 순회 방법은 특정 작업(예: 트리의 노드 출력, 데이터 검색 등)을 수행하기 위해 선택적으로 사용할 수 있습니다. 선택하는 순회 방법은 해당 작업의 목적과 요구 사항에 따라 달라질 수 있습니다.