백준 1991번 : 트리 순회 in Python
이 문제는 이진 트리를 입력받았을 때 해당 트리를 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 문제이다.
우선 이진 트리를 어떤 방식으로 구현해야 할지 고려해야 한다. 이진 트리의 각 노드에 반드시 필요한 요소로는 노드의 이름, 노드의 왼쪽 자식 노드, 그리고 노드의 오른쪽 자식 노드가 있다. 여기서는 트리 내 모든 노드들이 이름으로 서로 다른 알파벳을 가지기 때문에, 노드를 정의할 때 노드의 이름, 왼쪽 자식의 이름, 오른쪽 자식의 이름을 가지는 Node 클래스의 인스턴스로 정의한다.
그 다음에 주어진 데이터를 바탕으로 트리를 구성할 때에는 우선 tree라는 dictionary를 만든다. 이 dictionary는 key로 알파벳을 가지고, value로 그 알파벳을 이름으로 가지는 노드를 가진다. 그러므로 만약 데이터가 A B C와 같이 주어지면 tree['A']를 이름이 A, 왼쪽 자식의 노드의 이름이 B, 오른쪽 자식의 노드의 이름이 C인 Node 클래스의 인스턴스로 한다. 이렇게 해서 트리를 구현했을 때, 만약 특정 알파벳에 대응하는 노드를 찾고 싶다면 tree에서 해당 알파벳에 대응하는 값을 찾으면 되고, 자식 노드를 찾고 싶다면 해당 노드의 자식 노드의 이름을 찾아 tree에서 그 이름에 대응하는 노드를 찾으면 된다. 예를 들어 'A'의 왼쪽 자식 노드를 알고 싶다면 tree[tree['A'].left]로 찾을 수 있다.(여기서 left는 tree['A']의 인스턴스에서 왼쪽 자식 노드의 이름을 의미한다.)
이렇게 Node를 구현하기만 하면 순회를 구현하는 것은 그리 어렵지 않다. 순회는 루트 노드와 왼쪽 자식 트리, 그리고 오른쪽 자식 트리를 어떤 순서대로 방문하는지에 따라 크게 세 가지로 나뉜다. 전위 순회(preorder traversal)는 루트 -> 왼쪽 자식 -> 오른쪽 자식 순서대로 순회하고, 중위 순회(inorder traversal0는 왼쪽 자식 -> 루트 -> 오른쪽 자식 순서대로 순회하며, 후위 순회(postorder traversal)는 왼쪽 자식 -> 오른쪽 자식 -> 루트 순서대로 순회한다.
이러한 순회를 구현할 때는 재귀함수를 이용한다. 예를 들어 전위 순회의 경우 우선 루트 노드의 이름을 출력하고, 왼쪽 자식이 있는 경우 왼쪽 자식에 대해 다시 전위 순회를 수행한 뒤, 오른쪽 자식이 있는 경우 오른쪽 자식에 대해 다시 전위 순회를 수행한다. 이때 전위 순회를 다시 수행한다는 것은 전위 순회 함수를 재귀적으로 반복해서 호출한다는 의미이다. 이러한 방식으로 중위 순회, 후위 순회도 루트 노드의 이름을 출력하는 코드를 옮김으로써 쉽게 구현할 수 있다.
이를 코드로 구현하면 다음과 같다.
class Node:
def __init__(self, name, left, right):
# 왼쪽 자식 노드의 이름
self.left = left
# 오른쪽 자식 노드의 이름
self.right = right
# 노드의 이름
self.name = name
N = int(input())
# 트리를 저장할 dictionary
tree = {}
for _ in range(N):
a, b, c = map(str, input().split())
tree[a] = Node(name=a, left=b, right=c)
# 전위 순회 함수
def preorder(root):
print(root.name,end='')
if root.left != '.':
preorder(tree[root.left])
if root.right != '.':
preorder(tree[root.right])
# 중위 순회 함수
def inorder(root):
if root.left != '.':
inorder(tree[root.left])
print(root.name,end='')
if root.right != '.':
inorder(tree[root.right])
# 후위 순회 함수
def postorder(root):
if root.left != '.':
postorder(tree[root.left])
if root.right != '.':
postorder(tree[root.right])
print(root.name,end='')
preorder(tree['A'])
print()
inorder(tree['A'])
print()
postorder(tree['A'])
print()