트리 순회

트리 순회(Tree Traversal)는 트리(Tree) 구조에서 모든 노드를 특정한 순서에 따라 방문하는 방법이다. 트리 순회는 탐색, 정렬, 표현식 계산 등 다양한 응용에서 사용된다.

순회의 종류

트리 순회는 크게 깊이 우선 탐색(DFS, Depth-First Search)과 너비 우선 탐색(BFS, Breadth-First Search)으로 구분된다.

깊이 우선 탐색 (DFS)

DFS는 트리의 한쪽 끝까지 탐색한 후 백트래킹하는 방식으로, 다음 세 가지 방법이 있다.

• 전위 순회 (Preorder Traversal)
  • 순서: 루트 → 왼쪽 서브트리 → 오른쪽 서브트리
  • 수식 표현: V → L → R
  • 예제:
    • 주어진 트리
      • 전위 순회 결과: A → B → D → E → C → F

      A
     / \
    B   C
   / \   \
  D   E   F

• 중위 순회 (Inorder Traversal)
  • 순서: 왼쪽 서브트리 → 루트 → 오른쪽 서브트리
  • 수식 표현: L → V → R
  • 예제:
    • 중위 순회 결과: D → B → E → A → C → F

• 후위 순회 (Postorder Traversal)
  • 순서: 왼쪽 서브트리 → 오른쪽 서브트리 → 루트
  • 수식 표현: L → R → V
  • 예제:
    • 후위 순회 결과: D → E → B → F → C → A

너비 우선 탐색 (BFS)

BFS는 루트에서 시작하여 같은 깊이의 노드를 먼저 방문하는 방식이다.

• 레벨 순회 (Level Order Traversal)
  • 순서: 레벨(깊이) 순서대로 방문
  • 예제:
    • 레벨 순회 결과: A → B → C → D → E → F

순회의 응용

• 전위 순회
  • 표현식 트리에서 접미 표기법(Polish Notation) 변환.

• 중위 순회
  • 이진 탐색 트리(BST)에서 정렬된 순서로 출력 가능.

• 후위 순회
  • 디렉토리 구조 삭제, 수식 계산 등에 사용됨.

• 레벨 순회
  • 최단 경로 탐색 및 그래프 알고리즘에서 활용됨.

같이 보기

• 이진 트리
• 이진 탐색 트리
• 그래프 탐색
• 깊이 우선 탐색 (DFS)
• 너비 우선 탐색 (BFS)

참고 문헌

• Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms. MIT Press.