[자료구조] 트리 순회 - 재귀구조 DFS로 preoder, inorder, postorder 구현 (Python)

• 트리 순회

: 그래프 순회의 일종으로 각 노드를 정확히 한 번씩 방문하는 과정

: DFS, BFS로 탐색할 수 있으며, DFS 탐색의 경우 전위, 중위, 후위 순회가 있음

1) 전위 순회 (NLR)

 

# 전위 순회 (NLR)
def preorder(node):
    if node is None:
        return 
    print(node.val)
    preorder(node.left)
    preorder(node.right)

 

 

2) 중위 순회 (LNR)

 

# 중위 순회 (LNR)
def inorder(node):
    if node is None:
        return 
    inorder(node.left)
    print(node.val)
    inorder(node.right)

 

 

 

3) 후위 순회 (LRN)

 

# 후위 순회 (LRN)
def postorder(node):
    if node is None:
        return
    postorder(node.left)
    postorder(node.right)
    print(node.val)

같은 순회 매커니즘을 반복 구조로 구현할 수도 있지만, 트리의 재귀적 특성상 재귀 표현이 더 간결하고 직관적임.