[CS 기초 10] 자료구조 - 트리의 노드를 어떤 순서로 방문할까

thenullpage.com

1. 갈래가 있으면 순서를 정해야 합니다

리스트는 앞에서 뒤로 한 번 훑으면 모든 값을 봅니다. 트리는 다릅니다. 노드마다 왼쪽과 오른쪽으로 갈래가 갈리니 어느 쪽을 먼저 볼지, 자기 값은 언제 꺼낼지 정해야 합니다. 모든 노드를 빠짐없이 한 번씩 들르는 이 일을 순회(traversal)라고 합니다.

방식은 크게 둘입니다. 한 갈래를 끝까지 파고들었다가 돌아 나오는 깊이 우선, 그리고 위층부터 한 층씩 훑는 너비 우선입니다. 깊이 우선은 자기 값을 꺼내는 시점에 따라 전위, 중위, 후위 셋으로 다시 나뉩니다.

실습에 쓸 트리를 먼저 만들겠습니다. 값 하나와 왼쪽, 오른쪽 자리를 가진 노드를 이어 붙이면 됩니다.

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

root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.right = Node(6)

1 아래에 2와 3이 있고, 2 아래에 4와 5, 3의 오른쪽에 6이 붙었습니다. 이 여섯 개를 서로 다른 순서로 꺼내 보겠습니다.

2. 전위 순회는 자기부터 꺼냅니다

전위 순회(preorder)는 자기 값을 먼저 꺼내고, 왼쪽으로 내려갔다가, 오른쪽으로 내려갑니다.

def preorder(node):
if node is None:
return
print(node.value, end=" ")
preorder(node.left)
preorder(node.right)

preorder(root)

1 2 4 5 3 6

세 줄 순서가 전부입니다. 노드가 None이면 아무것도 하지 않고 돌아오는 종료 조건이 있어야 끝없이 내려가지 않습니다. print의 end=" "는 줄을 바꾸지 말고 공백을 붙이라는 뜻이라 결과가 한 줄로 나옵니다.

결과를 보면 부모가 자식보다 항상 먼저 나옵니다. 트리를 그대로 복사하거나 구조를 파일에 적어둘 때 이 순서를 씁니다.

3. 중위 순회는 왼쪽을 먼저 비웁니다

중위 순회(inorder)는 왼쪽을 다 본 뒤에 자기 값을 꺼내고 오른쪽으로 갑니다. print 줄의 위치만 가운데로 옮기면 됩니다.

def inorder(node):
if node is None:
return
inorder(node.left)
print(node.value, end=" ")
inorder(node.right)

inorder(root)

4 2 5 1 3 6

여기서 오해가 하나 생깁니다. 중위 순회를 하면 값이 정렬되어 나온다는 말을 자주 듣는데, 위 결과는 4 2 5로 시작해 전혀 정렬되어 있지 않습니다. 정렬되어 나오는 것은 왼쪽에 작은 값, 오른쪽에 큰 값이라는 조건을 지키는 이진 탐색 트리일 때뿐입니다.

bst = Node(5)
bst.left = Node(3)
bst.right = Node(8)
bst.left.left = Node(1)

inorder(bst)

1 3 5 8

같은 함수인데 이번에는 오름차순입니다. 순서 조건을 지킨 트리라 왼쪽을 먼저 비우는 것이 곧 작은 값부터 꺼내는 것이 됩니다. 어떤 트리가 이진 탐색 트리인지 검사할 때 중위 순회 결과가 계속 커지는지 보는 방법을 쓰는 이유입니다.

4. 후위 순회는 자식을 다 처리한 뒤에 꺼냅니다

후위 순회(postorder)는 왼쪽과 오른쪽을 모두 마친 다음 자기 값을 꺼냅니다.

def postorder(node):
if node is None:
return
postorder(node.left)
postorder(node.right)
print(node.value, end=" ")

postorder(root)

4 5 2 6 3 1

루트인 1이 맨 마지막에 나옵니다. 자식의 결과가 다 나와야 부모를 처리할 수 있는 일에 이 순서가 필요합니다. 폴더 용량은 안쪽 파일 크기를 먼저 더해야 바깥 폴더 크기가 나오고, 트리를 지울 때도 자식부터 지워야 합니다.

세 순회의 코드에서 다른 곳은 print 한 줄의 위치뿐입니다. 앞에서 꺼내면 전위, 가운데면 중위, 뒤면 후위이고, 노드를 한 번씩만 들르므로 셋 다 O(n)입니다.

5. 레벨 순회는 큐를 씁니다

층 단위로 보고 싶을 때는 재귀가 맞지 않습니다. 먼저 꺼낸 노드의 자식을 뒤에 쌓아두었다가 차례로 꺼내야 하니 선입선출인 큐가 필요합니다.

from collections import deque

def level_order(node):
q = deque([node])
result = []
while q:
level = []
for _ in range(len(q)):
cur = q.popleft()
level.append(cur.value)
if cur.left:
q.append(cur.left)
if cur.right:
q.append(cur.right)
result.append(level)
return result

print(level_order(root))

[[1], [2, 3], [4, 5, 6]]

바깥 반복문이 한 바퀴 돌 때마다 한 층이 끝납니다. 요령은 for 줄의 len(q)입니다. 반복을 시작하는 시점에 큐에 들어 있는 개수가 곧 이번 층의 노드 수라, 그만큼만 꺼내면 아래층 노드가 섞이지 않습니다. 이 길이를 재두지 않고 큐가 빌 때까지 그냥 꺼내면 층 구분 없이 한 줄로만 나옵니다.

6. 재귀 대신 스택으로 도는 방법

깊이 우선 순회는 재귀가 짧지만 함수를 부를 때마다 호출 정보가 쌓입니다. 한쪽으로 늘어진 트리에서는 이 깊이가 노드 수만큼 커져 파이썬 기본 한도인 1000단계 근처에서 RecursionError가 납니다. 그럴 때는 스택을 직접 만들어 씁니다.

def preorder_stack(node):
stack = [node]
while stack:
cur = stack.pop()
print(cur.value, end=" ")
if cur.right:
stack.append(cur.right)
if cur.left:
stack.append(cur.left)

preorder_stack(root)

1 2 4 5 3 6

재귀 버전과 결과가 같습니다. 눈여겨볼 곳은 오른쪽을 먼저 넣는 부분입니다. 스택은 나중에 넣은 것이 먼저 나오니, 왼쪽을 먼저 꺼내려면 오른쪽을 아래에 깔아야 합니다. 두 줄의 순서를 바꾸면 1 3 6 2 5 4가 나옵니다.

7. 순회에서 챙길 것

어디에 무엇을 쓰는지 정리하면 이렇습니다. 부모를 먼저 처리해야 하면 전위, 정렬된 순서로 값을 보고 싶으면 이진 탐색 트리에 중위, 자식 결과를 모아 부모를 계산하려면 후위, 층이나 최단 거리를 따져야 하면 레벨 순회입니다. 각 층의 최댓값이나 오른쪽에서 보이는 노드를 찾는 문제는 레벨 순회 뼈대에서 level 리스트만 손보면 끝납니다.

챙길 것은 세 가지입니다. 전위와 중위와 후위의 차이는 자기 값을 꺼내는 시점 하나뿐이라는 것, 중위 순회가 오름차순이 되는 것은 이진 탐색 트리일 때뿐이라는 것, 층 단위로 보려면 재귀가 아니라 큐를 쓰고 층의 시작에서 큐 길이를 재둔다는 것입니다.