백준 1991번 트리 순회 - python

문제 내용

문제 입력 및 출력

해당 문제는 이진 트리의 전위 순회, 중위 순회, 후위 순회를 이해하고 있는지에 대한 문제라고 생각한다.

재귀를 이용해서 문제를 풀어 나갔는데, edge의 node들을 defaultdict에 리스트 형태로 저장해서 탐색을 진행해 나갔다.

 

순회하는 방식은 동일하지만 언제 출력을 진행하는 가에 차이에 따라 전위, 중위, 후위가 결정 된다.

 

그래서 아래의 함수를 보면 동일한 방식을 채택하고 있지만, 출력문의 위치만 다른 것을 볼 수 있다.

 

def pre_order(n):
    if n != '.':
        print(n, end='')
        pre_order(edge[n][0])
        pre_order(edge[n][1])


def in_order(n):
    if n != '.':
        in_order(edge[n][0])
        print(n, end='')
        in_order(edge[n][1])


def post_order(n):
    if n != '.':
        for v in edge[n]:
            post_order(v)
        print(n, end='')


from collections import defaultdict

V = int(input())
edge = defaultdict(list)

for _ in range(V):
    parent, *child = input().split()
    edge[parent] = child

pre_order('A')
print()
in_order('A')
print()
post_order('A')

 

 

이 글이 도움 되셨다면,