[BOJ/백준] 1991 트리 순회

def preorder(key):
    if tree[key] == ('.','.'):
        result[0] += key
        return
    result[0] += key
    if tree[key][0] != '.':
        preorder(tree[key][0])
    if tree[key][1] != '.':
        preorder(tree[key][1])

def inorder(key):
    if tree[key] == ('.','.'):
        result[1] += key
        return
    if tree[key][0] != '.':
        inorder(tree[key][0])
    result[1] += key
    if tree[key][1] != '.':
        inorder(tree[key][1])
def postorder(key):
    if tree[key] == ('.','.'):
        result[2] += key
        return
    if tree[key][0] != '.':
        postorder(tree[key][0])
    if tree[key][1] != '.':
        postorder(tree[key][1])
    result[2] += key


tree = {}


N = int(input())
for _ in range(N):
    root,left,right = input().split()
    tree[root] = (left,right)
result = ['','','']
preorder('A')
inorder('A')
postorder('A')

for answer in result:
    print(answer)

트리의 대표적인 순회 종류인 전위, 중위, 후위 탐색기법을 적용시킨 것이다. 트리에 대해서 아직 잘 몰라, 실제 이진 트리를 만들면서 더 연습해봐야겠다.

 

일단 풀이는 재귀방식을 이용해서, 구해줬다. 일단 

전위 순회 방식은 (루트 -> 왼쪽 -> 오른쪽 자식) 이므로, 함수를 돌릴때 root에 해당되는 함수에 들어온 key를 결과값에 넣어주고, 그 다음에 왼쪽 , 오른쪽 순으로 함수를 재귀적으로 실행시켜줬다.

 

중위 순회는 왼쪽 -> 루트 -> 오른쪽 순으로 해줬다.

 

후위 순회는 왼쪽 -> 오른쪽 -> 루트  순으로 해줬다.