티스토리 뷰

카테고리 없음

이진트리 순회 원리 (전위, 중위, 후위)

머니지니87 2026. 2. 1. 12:58

목차


    반응형

    이진트리 순회 원리

    배열(Array)이나 연결 리스트(Linked List)와 같은 선형 자료구조는 데이터가 일렬로 나열되어 있어 순회(Traversal) 방법이 직관적입니다. 단순히 인덱스를 0부터 끝까지 증가시키면 되기 때문입니다. 하지만 이진트리(Binary Tree)는 계층적(Hierarchical)이고 비선형적인 구조를 가지므로, 모든 노드를 빠짐없이 중복 없이 방문하기 위해서는 명확한 규칙과 알고리즘이 필요합니다. 트리를 순회하는 방법은 루트(Root) 노드를 언제 방문하느냐에 따라 전위(Pre-order), 중위(In-order), 후위(Post-order) 세 가지로 나뉘며, 이는 DFS(깊이 우선 탐색)의 기초가 되는 매우 중요한 개념입니다.

    1. 순회(Traversal)의 기본 개념과 재귀적 특성

    이진트리 순회의 핵심은 재귀(Recursion)입니다. 트리는 '루트', '왼쪽 서브 트리', '오른쪽 서브 트리'로 구성되어 있고, 서브 트리 역시 또 다른 트리 구조를 가집니다. 따라서 전체 트리를 순회하는 문제는 '서브 트리를 어떻게 순회할 것인가'라는 작은 문제로 쪼개집니다. 순회 방식의 이름(전위, 중위, 후위)은 루트 노드를 방문하는 순서에 따라 결정됩니다.

    2. 전위 순회 (Pre-order Traversal)

    전위 순회는 "루트(Root)를 가장 먼저" 방문하는 방식입니다. 트리의 구조를 그대로 복사하거나, 수식의 전위 표기법(Prefix Notation)을 구할 때 사용됩니다.

    2-1. 방문 순서 (N-L-R)

    1. Node: 현재 노드(루트)를 먼저 방문(처리)합니다.
    2. Left: 현재 노드의 왼쪽 서브 트리를 전위 순회합니다.
    3. Right: 현재 노드의 오른쪽 서브 트리를 전위 순회합니다.

    3. 중위 순회 (In-order Traversal)

    중위 순회는 "루트(Root)를 중간에" 방문하는 방식입니다. 왼쪽 끝까지 내려갔다가 올라오면서 처리하는 흐름을 가집니다. 이 방식의 가장 큰 특징은 이진 탐색 트리(BST)에 적용했을 때, 데이터가 오름차순으로 정렬된 결과를 얻을 수 있다는 점입니다.

    3-1. 방문 순서 (L-N-R)

    1. Left: 현재 노드의 왼쪽 서브 트리를 중위 순회합니다.
    2. Node: 왼쪽 탐색이 끝나면 현재 노드(루트)를 방문합니다.
    3. Right: 현재 노드의 오른쪽 서브 트리를 중위 순회합니다.

    4. 후위 순회 (Post-order Traversal)

    후위 순회는 "루트(Root)를 가장 나중에" 방문하는 방식입니다. 자식 노드들을 모두 처리한 뒤에야 부모 노드를 처리하므로, 트리의 삭제(메모리 해제)나 수식 트리의 계산, 폴더 용량 계산 등에 활용됩니다. 자식을 지우기 전에 부모를 지우면 안 되기 때문입니다.

    4-1. 방문 순서 (L-R-N)

    1. Left: 현재 노드의 왼쪽 서브 트리를 후위 순회합니다.
    2. Right: 현재 노드의 오른쪽 서브 트리를 후위 순회합니다.
    3. Node: 자식들의 방문이 모두 끝나면 현재 노드(루트)를 방문합니다.

    5. 파이썬(Python) 코드 구현 및 비교

    재귀 함수를 이용하면 세 가지 순회 방식을 매우 간결하게 구현할 수 있습니다. print(방문 처리)문의 위치가 어디에 있느냐에 따라 순회 방식이 결정됩니다.

    
class Node:
    def __init__(self, item):
        self.item = item
        self.left = None
        self.right = None

# 1. 전위 순회 (Pre-order): Root -> Left -> Right
def preorder(node):
    if node:
        print(node.item, end=' ')  # 방문 (먼저)
        preorder(node.left)        # 왼쪽 이동
        preorder(node.right)       # 오른쪽 이동

# 2. 중위 순회 (In-order): Left -> Root -> Right
def inorder(node):
    if node:
        inorder(node.left)         # 왼쪽 이동
        print(node.item, end=' ')  # 방문 (중간)
        inorder(node.right)        # 오른쪽 이동

# 3. 후위 순회 (Post-order): Left -> Right -> Root
def postorder(node):
    if node:
        postorder(node.left)       # 왼쪽 이동
        postorder(node.right)      # 오른쪽 이동
        print(node.item, end=' ')  # 방문 (나중)

# 트리 구성 및 테스트
#      1
#     / \
#    2   3
root = Node(1)
root.left = Node(2)
root.right = Node(3)

print("Pre-order: ", end='')
preorder(root)   # 출력: 1 2 3
print("\nIn-order:  ", end='')
inorder(root)    # 출력: 2 1 3
print("\nPost-order:", end='')
postorder(root)  # 출력: 2 3 1
    [핵심 요약 : 이진트리 순회 3대장]
    1. 전위(Pre): 루트 선방문(N-L-R). 트리 복사나 구조 파악에 유리합니다.
    2. 중위(In): 루트 중간방문(L-N-R). 이진 탐색 트리(BST)를 정렬된 순서로 읽을 때 필수적입니다.
    3. 후위(Post): 루트 후방문(L-R-N). 하위 노드부터 처리해야 하는 메모리 해제나 폴더 용량 계산에 사용됩니다.
    반응형