트리 순회(백준 1991번)

💡 **Check Point !

( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?✓

---

난이도 체감

1. 최상

2. 상

3. 중✓

4. 하

---

이해도

1. 완벽히 이해✓

2. 다소 헷갈리는 부분들이 있음

3. 이해 못함

문제

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

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

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

가 된다.

나의 풀이(정답 참고)

import sys

def preorder(tree_dic,node):
    if node!='.':
        print(node,end='')
        preorder(tree_dic,tree_dic[node][0])
        preorder(tree_dic,tree_dic[node][1])
    
def inorder(tree_dic,node):
    if node!='.':
        inorder(tree_dic,tree_dic[node][0])
        print(node,end='')
        inorder(tree_dic,tree_dic[node][1])

def postorder(tree_dic,node):
    if node!='.':
        postorder(tree_dic,tree_dic[node][0])
        postorder(tree_dic,tree_dic[node][1])
        print(node,end='')

N=int(input())
tree_dic=dict()
for _ in range(N):
    node,L,R=sys.stdin.readline().strip().split()
    tree_dic[node]=[L,R]
preorder(tree_dic,'A')
print('')
inorder(tree_dic,'A')
print('')
postorder(tree_dic,'A')
print('')

• 위 문제는 백준 22856번 문제를 풀기 전, 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)의 개념을 익히기 위해 풀어본 문제이다.
• BFS와 DFS를 잘 이해했기 때문에, 비교적 쉽게 위 알고리즘을 이해할 수 있었다.
• 개념은 아래 내용을 보면 될 것 같다.

트리 순회(전위 순회, 중위 순회, 후위 순회)