[TIL] 104. [자료구조] 순회

키워드

• 순회(트리 : 전위/중위/후위, 그래프 : BFS/DFS)

순회(Traversal)

• 트리, 그래프와 같이 연결된 자료구조에서 모든 노드를 한 번씩 탐색하는 것
• 순회의 목적 : 모든 혹은 특정 노드를 방문하는 방법을 찾는 것
• 방향에 따라 순회하는 방법이 달라진다.

[순회] 트리구조

• 트리 구조에서의 순회는 크게 전위, 중위, 후위로 나누어진다.

• 전위 : 1. Root node -> 2. Left node -> 3. Right node
• 중위 : 1. Left node -> 2. Root node -> 3. Right node
• 후위 : 1. Left node -> 2. Right node -> 3. Root node
• 단순하게 왼쪽에서 오른쪽이면서 Root node의 위치에 따라 나누어진다고 생각하면 쉽다.

# 재귀함수를 사용한 트리구조 순회

## 전위

def pre_order(node):
    print(node.value)
    pre_order(node.left)
    pre_order(node.right)

## 중위

def in_order(node):
    in_order(node.left)
    print(node.value)
    in_order(node.right)

## 후위

def post_order(node):
    post_order(node.left)
    post_order(node.right)
    print(node.value)