(Python) - BOJ(1991번) : 트리 순회

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

1991번: 트리 순회

---

• 문제 : 

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

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

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

 

 

 

---

• 풀이 :

루트 노드인 "A"에서부터 전위, 중위, 후위 순회를 진행한다. 이 때, left 또는 right가 "." 일경우 진행하지 않는다.

 

 

 

---

• 소스코드 : 

N = int(input())
tree = dict()
for _ in range(N):
    parent,left,right = input().split()
    tree[parent] = {
        "left" : left,
        "right" : right
    }
def preorder(curr):
    if curr != ".":
        print(curr,end="")
        preorder(tree[curr]["left"])
        preorder(tree[curr]["right"])

def inorder(curr):
    if curr != ".":
        inorder(tree[curr]["left"])
        print(curr,end="")
        inorder(tree[curr]["right"])

def postorder(curr):
    if curr != ".":
        postorder(tree[curr]["left"])
        postorder(tree[curr]["right"])
        print(curr,end="")

preorder("A")
print("")
inorder("A")
print("")
postorder("A")