Tree Traversal - Pre-order, In-order, Post-order

Tree를 순회하는 방법에는 세가지가 있다.

1. Pre-order Traversal (전위순회법)

• Root node에서 시작하여
• 왼쪽 부 트리를 순회하고 가장 마지막의 부트리까지 순회한다
• 오른쪽 부 트리를 순회하고 가장 마지막의 부트리까지 순회한다.

DFS와 비슷한 논리라고 생각하면 쉽다.

출처: SWEA Tree

Pseudocode: Pre_order

def pre_order(T):
	
    if T is not null:
    	visit(T)
        pre_order(T.left)
        pre_order(T.right)

 

2. In-Order Traversal (중위 순회법)

• 트리의 가장 왼쪽 노드로 이동한다.
• 왼쪽 노드의 루트를 탐색한다.
• 루트의 오른쪽 노드를 탐색한다.

트리의 가장 왼쪽에 있는 노드부터 시작하여 탐색한다고 생각하면 이해가 쉽다.

출처: SWEA Tree

def in_order(T):
	
    if T is not null:
        in_order(T.left)
        visit(T)
        in_order(T.right)

 

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

• 현재 노드의 왼쪽 부트리에서 시작
• 현재 노드의 오른쪽 부트리로 이동
• 현재 노드 방문하여 처리

출처: SWEA Tree

def post_order(T):
	
    if T is not null:
        post_order(T.left)
        post_order(T.right)
        visit(T)