트리 순회 편집하기

'''트리 순회'''(Tree Traversal)는 트리(Tree) 구조에서 모든 노드를 특정한 순서에 따라 방문하는 방법이다.  트리 순회는 탐색, 정렬, 표현식 계산 등 다양한 응용에서 사용된다.
==순회의 종류==
트리 순회는 크게 '''깊이 우선 탐색(DFS, Depth-First Search)'''과 '''너비 우선 탐색(BFS, Breadth-First Search)'''으로 구분된다.
===깊이 우선 탐색 (DFS)===
DFS는 트리의 한쪽 끝까지 탐색한 후 백트래킹하는 방식으로, 다음 세 가지 방법이 있다.
*'''전위 순회 (Preorder Traversal)'''
**순서: 루트 → 왼쪽 서브트리 → 오른쪽 서브트리
**수식 표현: V → L → R
**예제:
***주어진 트리
****전위 순회 결과: A → B → D → E → C → F
<pre>
      A
     / \
    B   C
   / \   \
  D   E   F
</pre>
***

*'''중위 순회 (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.