이진 트리 순회 (Binary Tree Traversal)

이진 트리 순회 (Binary Tree Traversal)

이진 트리의 모든 노드를 체계적으로 방문하는 방법으로, 노드·왼쪽·오른쪽 방문 순서에 따라 전위·중위·후위·레벨 순회로 구분

목적: 트리 노드 방문, 데이터 처리, 트리 복사/비교, 수식 변환

특징: 재귀적/반복적 구현, DFS(전위/중위/후위), BFS(레벨)

순회 방식

• •전위 순회(Preorder): 노드 → 왼쪽 → 오른쪽 (NLR), 복사/직렬화에 활용
• •중위 순회(Inorder): 왼쪽 → 노드 → 오른쪽 (LNR), BST에서 정렬된 순서 출력
• •후위 순회(Postorder): 왼쪽 → 오른쪽 → 노드 (LRN), 삭제/메모리 해제에 활용
• •레벨 순회(Level-order): 레벨별 좌→우, BFS 사용, 큐 활용

구현 방법

• •재귀: 간결하고 직관적, 스택 오버플로우 위험
• •반복(스택): 전위/중위/후위 구현, 명시적 스택 사용
• •반복(큐): 레벨 순회, FIFO 사용

Morris Traversal: O(1) 공간 중위 순회, 스레드 이진 트리 개념 활용

시간 복잡도: 모든 순회 O(n)

공간 복잡도: 재귀 O(h), 반복 O(h), Morris O(1) [h=높이]

수식 트리 활용

• •전위 순회 → 전위 표기법 (+ A B)
• •중위 순회 → 중위 표기법 (A + B)
• •후위 순회 → 후위 표기법 (A B +)

장점: 트리 데이터 체계적 처리, 다양한 응용

단점: 재귀 시 스택 오버플로우, 깊은 트리에서 메모리

적용사례: 컴파일러(수식 트리), 파일 시스템, XML/JSON 파싱, 트리 직렬화

비교: 전위(복사) vs 중위(정렬) vs 후위(삭제) vs 레벨(BFS)

연관: 이진 트리, DFS, BFS, 스택, 큐, 수식 트리