1991_트리 순회

https://www.acmicpc.net/problem/1991

1991번: 트리 순회

처음 보면 조금 헤맬 수 있는 문제이다.

 

트리 구조에 대해서 약간 공부를 하고 순회하는 법에 대해서 공부를 한 후 풀 수 있었다.

 

리스트를 통해 현재노드와 자식 노드들을 저장하는것까지는 생각을 했는데 순회방법을 몰라서 헤맸었다.

 

알고보니 결국 탐색을 위해선 dfs방식을 택하는데 이때 print해주는 위치에 따라서 전위,중위,후위탐색이 되는 것이었다.

 

n = int(input())
tree = [ [0,0,0] for _ in range(n)]

for _ in range(n):
    node,left,right = map(str,input().split())
    idx = ord(node)-ord('A')
    tree[idx]= [node,left,right]

def pre(node):
    idx = ord(node)-ord('A')
    print(node,end='')
    if tree[idx][1] != ".":
        pre(tree[idx][1])
    if tree[ord(node)-ord('A')][2] != ".":
        pre(tree[idx][2])
def middle(node):
    idx = ord(node)-ord('A')

    if tree[idx][1] != ".":
        middle(tree[idx][1])
    print(node,end='')
    if tree[ord(node)-ord('A')][2] != ".":
        middle(tree[idx][2])
def post(node):
    idx = ord(node)-ord('A')
    if tree[idx][1] != ".":
        post(tree[idx][1])
    if tree[ord(node)-ord('A')][2] != ".":
        post(tree[idx][2])
    print(node, end='')



pre('A')
print()
middle('A')
print()
post('A')