트리 순회

트리 순회(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)

순회 예

일반 이진 트리

전위(V→L→R): A B D C E F
중위(L→V→R): D B A E C F
후위(L→R→V): D B E F C A
순서마다 루트를 언제 방문하느냐만 다르다. 중위 순회는 왼쪽 서브트리(D B)를 다 돈 뒤 루트 A, 그다음 오른쪽 서브트리(E C F)를 돈다

수식 트리

연산자를 내부 노드, 피연산자를 단말 노드로 둔 트리다. 수식 ((A / B) * C) * D + E 는 루트가 +, + 의 왼쪽이 *, 그 왼쪽이 다시 *, 그 왼쪽이 / 이고 / 의 자식이 A·B 이다.

전위 순회: + * * / A B C D E (전위 표기)
중위 순회: A / B * C * D + E (괄호를 빼면 원래 수식)
후위 순회: A B / C * D * E + (후위 표기, 스택으로 계산할 때 쓴다) → 후위식

순회의 응용

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

같이 보기

참고 문헌

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