Tree 탐색 방법에는 어떤 것들이 있나요?

[eunjungL]

.

[Chocochip101]

Tree 탐색을 할 때 주로 사용하는 방법들은 다음과 같습니다.

전위 순회

• 순서: 노드 → 왼쪽 서브트리 → 오른쪽 서브트리

  public void preOrder(TreeNode node) {
      if (node == null) return;
      System.out.print(node.value + " ");
      preOrder(node.left);
      preOrder(node.right);
  }

중위 순회

• 순서: 왼쪽 서브트리 → 노드 → 오른쪽 서브트리

  public void inOrder(TreeNode node) {
      if (node == null) return;
      inOrder(node.left);
      System.out.print(node.value + " ");
      inOrder(node.right);
  }

후위 순회

• 순서: 왼쪽 서브트리 → 오른쪽 서브트리 → 노드

  public void postOrder(TreeNode node) {
      if (node == null) return;
      postOrder(node.left);
      postOrder(node.right);
      System.out.print(node.value + " ");
  }

레벨 순회

• 순서: 트리의 각 레벨을 순차적으로 방문

  public void levelOrder(TreeNode root) {
      if (root == null) return;
      Queue<TreeNode> queue = new LinkedList<>();
      queue.add(root);
      while (!queue.isEmpty()) {
          TreeNode node = queue.poll();
          System.out.print(node.value + " ");
          if (node.left != null) queue.add(node.left);
          if (node.right != null) queue.add(node.right);
      }
  }

[PgmJun]

gif 링크

[PgmJun]

사용 용도

전위 순회

• 트리의 데이터 직렬화, 역직렬화.
  • 파일 시스템과 같은 계층 구조에서 구조 기록 및 복원

중위 순회

• 이진 탐색 트리에서 오름차순으로 트리를 조회할 때 사용

후위 순회

• 파일 시스템과 같은 계층 구조에서 하위의 디렉터리를 모두 제거하고 디렉터리를 제거하는 등의 작업에서 사용

레벨 순회

• 레벨 별 통계를 구하는 등 트리의 값을 각 레벨 단위로 처리해야할 때 사용