오늘 정리해 볼 내용은 '트리 순회' 입니다.
트리 순회(Tree Traversal)란,
트리(Tree) 자료구조의 노드(Node)를 방문하는 방법 중 하나입니다.
트리 순회는 트리 내의 모든 노드를 방문하는 방법으로,
노드의 값들을 순서대로 처리할 수 있습니다.
트리 순회에는 대표적으로 3가지가 있습니다.
트리 순회에는 전위 순회(preorder), 중위 순회(inorder), 후위 순회(postorder) 가 있습니다.
전위 순회는 [ 루트 - 왼쪽 자식 - 오른쪽 자식 ] 순서대로 순회합니다.
중위 순회는 [ 왼쪽 자식 - 루트 - 오른쪽 자식] 순서대로 순회합니다.
후위 순회는 [ 왼쪽 자식 - 오른쪽 자식 - 루트] 순서대로 순회합니다.
순서를 쉽게 외우는 방법을 알려드리자면,
영어 'order' 를 기준으로 앞에 있는 접두사에 초점을 맞추면 됩니다.
예를 들어, preorder(전위 순회) 는 루트가 제일 앞에,
inorder(중위 순회)는 루트가 중간에,
postorder(후위 순회)는 루트가 마지막에 나옵니다.
빈칸은 왼쪽 자식 - 오른쪽 자식 순서대로 채워주면 순서를 외우기 쉽습니다.
이 트리를 기준으로 3가지 순회 방법에 대해 설명해 보겠습니다.
트리 순회는 재귀 함수를 이용해 구현할 수 있습니다.
1. 전위 순회(preorder)
-
방문순서 : [ 루트 - 왼쪽 자식 - 오른쪽 자식 ]
-
자식 노드를 확인할 때는 왼쪽 노드부터 확인합니다.
-
결과 : 1 2 4 8 5 3 6 7
arr=' 12345678' # arr[0] 은 비어있는 칸임
def preorder(now):
if now>len(arr)-1: return
print(arr[now],end=' ') # 전위 순회니깐 앞에 print()
preorder(now*2) # 왼쪽 자식 노드 탐색
preorder(now*2+1) # 오른쪽 자식 노드 탐색
preorder(1) # 전위순회2. 중위 순회(inorder)
-
방문 순서 : [ 왼쪽 자식 - 루트 - 오른쪽 자식]
-
왼쪽 자식을 확인하고 루트를 확인한 뒤 오른쪽 자식을 확인합니다.
-
결과 : 8 4 2 5 1 6 3 7
arr=' 12345678'
def inorder(now):
if now > len(arr) - 1: return
inorder(now * 2)
print(arr[now], end=' ') # 중위 순회니깐 가운데에 print
inorder(now * 2 + 1)
inorder(1) # 중위순회3. 후위 순회(postorder)
-
방문 순서 : [ 왼쪽 자식 - 오른쪽 자식 - 루트]
-
결과 : 8 4 5 2 6 7 3 1
arr=' 12345678'
def postorder(now):
if now > len(arr) - 1: return
postorder(now * 2)
postorder(now * 2 + 1)
print(arr[now], end=' ') # 후위 순회니깐 뒤에 print()
postorder(1) # 후위순회