문제
이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 프로그램을 작성하시오.
예를 들어 위와 같은 이진 트리가 입력되면,
전위 순회한 결과 : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 자식)
중위 순회한 결과 : DBAECFG // (왼쪽 자식) (루트) (오른쪽 자식)
후위 순회한 결과 : DBEGFCA // (왼쪽 자식) (오른쪽 자식) (루트)
가 된다.
입력
첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파벳 대문자로 매겨지며, 항상 A가 루트 노드가 된다. 자식 노드가 없는 경우에는 .으로 표현한다.
출력
첫째 줄에 전위 순회, 둘째 줄에 중위 순회, 셋째 줄에 후위 순회한 결과를 출력한다. 각 줄에 N개의 알파벳을 공백 없이 출력하면 된다.
예제 입력 1
7
A B C
B D .
C E F
E . .
F . G
D . .
G . .
예제 출력 1
ABDCEFG
DBAECFG
DBEGFCA
문제 해결
Python으로는 트리를 어떻게 구현하는가?
많은 방법이 있겠지만(사실 있는지는 잘 모른다), 나는 Tree를 구현을 현재 시점으로는 구현을 해본 적이 없다.
그래서 다른 사람이 한 것을 참고해봤다.
일단 처음에 "어떻게 구현을 해야할까?" 하고 고민을 했다.
일단 이전에, 배열로 구현한 것을 본 것 같았고, 다른 여러가지 방법으로 구현한 것을 본 기억이 조금이나마 있었다.(진짜인지는 모른다.)
고민을 하다가, 일단 백준 트리 문제를 찾아서 풀어보기로 했다.
전위 순회, 중위 순회, 후위 순회로 노드를 출력하는 문제다.
그 문제를 어떻게 해결했는지, 어떻게 풀었는지, 그리고 트리를 어떤 자료구조에 담아서 해결을 할 생각을 했는지 궁금했다.
방법은 '딕셔너리'였다.
딕셔너리는 Key, Value를 담는 자료구조인데, 트리를 구현하기 위해선 Key에 Root node를, value에는 left, right node를 담아 구현을 하려고 했다.
위 사진을 예를 들면, 다음과 같다.
tree라는 딕셔너리 자료구조를 선언을 한 상태이다.
tree['A'] = ['B', 'C']
tree['B'] = ['D', .] (node가 없으면 .으로 표현한다.)
...
이러한 방식으로 구현한다.
따라서 처음에 딕셔너리에 담을 때는 다음과 같이 담았다.
N = int(input())
tree = {}
for _ in range(N) :
root, left, right = map(str, input().split())
tree[root] = [left, right]그리고 전위 순회, 중위 순회, 후위 순회로 출력하기 위해서는 재귀 함수를 이용해야한다.
이용한 방식은 다음과 같다.
def preorder(root) :
if root != '.' :
print(root, end='')
preorder(tree[root][0]) # left
preorder(tree[root][1]) # right
def inorder(root) :
if root != '.' :
inorder(tree[root][0]) # left
print(root, end='')
inorder(tree[root][1]) # right
def postorder(root) :
if root != '.' :
postorder(tree[root][0]) # left
postorder(tree[root][1]) # right
print(root, end='')전체 코드는 다음과 같다.
N = int(input())
tree = {}
for _ in range(N) :
root, left, right = map(str, input().split())
tree[root] = [left, right]
def preorder(root) :
if root != '.' :
print(root, end='')
preorder(tree[root][0])
preorder(tree[root][1])
def inorder(root) :
if root != '.' :
inorder(tree[root][0])
print(root, end='')
inorder(tree[root][1])
def postorder(root) :
if root != '.' :
postorder(tree[root][0])
postorder(tree[root][1])
print(root, end='')
preorder('A')
print()
inorder('A')
print()
postorder('A')