[알고리즘] 백준 1991 파이썬 - 트리 순회

 

1991번: 트리 순회

문제

 

이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 프로그램을 작성하시오.

예를 들어 위와 같은 이진 트리가 입력되면,

• 전위 순회한 결과 : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 자식)
• 중위 순회한 결과 : DBAECFG // (왼쪽 자식) (루트) (오른쪽 자식)
• 후위 순회한 결과 : DBEGFCA // (왼쪽 자식) (오른쪽 자식) (루트)

가 된다.

 

문제풀이

import sys
input = sys.stdin.readline
#01
n=int(input())
tmp={}
for _ in range(n):
    a,b,c=input().split()
    tmp[a]=[b,c]
#02
def pre(x):
    if x!=".":
        print(x,end="")
        pre(tmp[x][0])
        pre(tmp[x][1])
def In(x):
    if x!=".":
        In(tmp[x][0])
        print(x,end="")
        In(tmp[x][1])
def post(x):
    if x!=".":
        post(tmp[x][0])
        post(tmp[x][1])
        print(x,end="")
#03
pre('A')
print()
In('A')
print()
post('A')

- #01 : 주어진 입력대로 tmp에 루트와 left,right의 관계를 저장한다.

- #02 : 순서대로, 전위, 중위, 후위 순회를 진행할 수 있게 루트, left, right의 

           출력 순서를 조절하여 함수로 만든다.

- #03 : 모두 초기값은 "A"부터 시작하여 출력한다.