[백준BOJ] 1991번 트리 순회.py

 

백준 저지에서 트리 순회를 파이썬을 통해 풀어 보았다. 

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

1991번: 트리 순회

1991번 트리 순회.py

GitHub - tomy9729/Algorithm: 🐗 내가 직접 작성한 내 코드 🐗

 

 

1991번 트리 순회

문제

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

예를 들어 위와 같은 이진 트리가 입력되면,
전위 순회한 결과 : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 자식)
중위 순회한 결과 : DBAECFG // (왼쪽 자식) (루트) (오른쪽 자식)
후위 순회한 결과 : DBEGFCA // (왼쪽 자식) (오른쪽 자식) (루트)

설명

파이썬의 딕셔너리를 통해 부모 노드와 자식 노드를 연결해준다. 연결된 노드를 따라 각 순회에 맞춰 순서대로 출력해준다.

 

실질적인 트리는 아니지만 문제를 해결할 수 있다.

코드

#1991번 트리 순회.py
n = int(input())
tree = {}

for _ in range(n):
    root,left,right = 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')