트리 순회

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

순회의 종류

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

깊이 우선 탐색 (DFS)

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

전위 순회 (Preorder Traversal)

• 순서: 루트 → 왼쪽 서브트리 → 오른쪽 서브트리
• 수식 표현: V → L → R

슈도코드:

PreorderTraversal(node):
    if node is not null:
        visit(node)
        PreorderTraversal(node.left)
        PreorderTraversal(node.right)

파이썬 코드:

def preorder_traversal(node):
    if node is not None:
        print(node.value, end=" ")
        preorder_traversal(node.left)
        preorder_traversal(node.right)

중위 순회 (Inorder Traversal)

• 순서: 왼쪽 서브트리 → 루트 → 오른쪽 서브트리
• 수식 표현: L → V → R

슈도코드:

InorderTraversal(node):
    if node is not null:
        InorderTraversal(node.left)
        visit(node)
        InorderTraversal(node.right)

파이썬 코드:

def inorder_traversal(node):
    if node is not None:
        inorder_traversal(node.left)
        print(node.value, end=" ")
        inorder_traversal(node.right)

후위 순회 (Postorder Traversal)

• 순서: 왼쪽 서브트리 → 오른쪽 서브트리 → 루트
• 수식 표현: L → R → V

슈도코드:

PostorderTraversal(node):
    if node is not null:
        PostorderTraversal(node.left)
        PostorderTraversal(node.right)
        visit(node)

파이썬 코드:

def postorder_traversal(node):
    if node is not None:
        postorder_traversal(node.left)
        postorder_traversal(node.right)
        print(node.value, end=" ")

너비 우선 탐색 (BFS)

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

레벨 순회 (Level Order Traversal)

• 순서: 레벨(깊이) 순서대로 방문

슈도코드:

LevelOrderTraversal(root):
    queue = empty queue
    queue.enqueue(root)
    
    while queue is not empty:
        node = queue.dequeue()
        visit(node)
        if node.left is not null:
            queue.enqueue(node.left)
        if node.right is not null:
            queue.enqueue(node.right)

파이썬 코드:

from collections import deque

def level_order_traversal(root):
    if root is None:
        return
    
    queue = deque([root])
    while queue:
        node = queue.popleft()
        print(node.value, end=" ")
        
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)

순회의 응용

• 전위 순회 - 표현식 트리에서 접미 표기법(Polish Notation) 변환.
• 중위 순회 - 이진 탐색 트리(BST)에서 정렬된 순서로 출력 가능.
• 후위 순회 - 디렉토리 구조 삭제, 수식 계산 등에 사용됨.
• 레벨 순회 - 최단 경로 탐색 및 그래프 알고리즘에서 활용됨.

같이 보기

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

참고 문헌

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