[트리] 백준 1991번: 트리순회 (Python 파이썬)

💡문제 링크

1991번: 트리 순회

 

💡문제 분석 요약

전위 순회: 루트 노드 - 왼쪽 자식 노드 - 오른쪽 자식 노드 방문

중위 순회: 왼쪽 자식 노드 - 루트 노드 - 오른쪽 자식 노드 방문

후위 순회: 왼쪽 자식 노드 - 루트 노드 - 오른쪽 자식 노드 방문

첫째 줄에 이진 트리의 노드 개수가 입력되고, 둘째 줄부터 N개의 줄에 걸쳐 각 노드, 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다.

자식 노드가 없는 경우 .으로 표시한다.

전위 순회, 중위 순회, 후위 순회한 결과를 세 줄에 걸쳐 출력하는 문제.

💡알고리즘 설계

1. 입력값을 노드 형태로 받아들이는 코드가 필요하다. -> 딕셔너리 형태를 이용! tree["A"] = ["B", "C"]이면 A의 왼쪽 자식 노드가 B, 오른쪽 자식 노드가 C라는 소리

2. 전위 순회, 중위 순회, 후위 순회를 각각 수행하는 함수 3개를 만들어야 한다.

 

 

💡코드

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")
print()

 

💡 오답 풀이

...

 

💡 다른 풀이

...

 

💡 느낀점 or 기억할정보

...