[Python/백준] 트리 순회

 

전위 순회(preorder): A -> B -> C

중위 순회(inorder): B -> A -> C

후위 순회(postorder): B -> C -> A

 

 

---

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

 

---

재귀 함수를 이용

 

 

입력 및 트리 만들기

import sys
input = sys.stdin.readline

n = int(input())

tree = {}
for _ in range(n):
    a, b, c = input().split()
    tree[a] = [b,c] # 0번 인덱스는 왼쪽 1번 인덱스는 오른쪽
    
print(tree)

{'A': ['B', 'C'], 'B': ['D', '.'], 'C': ['E', 'F'], 'E': ['.', '.'], 'F': ['.', 'G'], 'D': ['.', '.'], 'G': ['.', '.']}

 

전위, 중위, 후위 함수 만들기

def preorder(node):
    print(node, end='') # 가운데
    if tree[node][0] != '.':
        preorder(tree[node][0]) # 왼쪽
    if tree[node][1] != '.':
        preorder(tree[node][1]) # 오른쪽
        
def inorder(node):
    if tree[node][0] != '.':
        inorder(tree[node][0]) # 왼쪽
    print(node, end='') # 가운데
    if tree[node][1] != '.':
        inorder(tree[node][1]) # 오른쪽
        
def postorder(node):
    if tree[node][0] != '.':
        postorder(tree[node][0]) # 왼쪽
    if tree[node][1] != '.':
        postorder(tree[node][1]) # 오른쪽
    print(node, end='') # 가운데

 

루트 넣어주기

preorder('A')
print()
inorder('A')
print()
postorder('A')