[BOJ] #1991 - 트리 순회

1991번: 트리 순회

 

 

** 문제 유형

• 트리, 구현

 

** 풀이

1. 전위 순회: 루트 -> 왼쪽 자식 -> 오른쪽 자식
2. 중위 순회: 왼쪽 자식 -> 루트 -> 오른쪽 자식 <왼쪽부터 차례대로 출력>
3. 후위 순회: 왼쪽 자식 -> 오른쪽 자식 -> 루트

 

class Node:
    def __init__(self, data, left_node, right_node):
        self.data = data
        self.left_node = left_node
        self.right_node = right_node

---

def pre_order(node): # 중 -> 왼 -> 오
    print(node.data, end = '')
    if node.left_node != '.':
        pre_order(tree[node.left_node])
    if node.right_node != '.':
        pre_order(tree[node.right_node])
        
def in_order(node): # 왼 -> 중 -> 오
    if node.left_node != '.':
        in_order(tree[node.left_node])
    print(node.data, end = '')
    if node.right_node != '.':
        in_order(tree[node.right_node])
        
def post_order(node): # 왼 -> 오 -> 중
    if node.left_node != '.':
        post_order(tree[node.left_node])
    if node.right_node != '.':
        post_order(tree[node.right_node])
    print(node.data, end = '')

---

n = int(input())

tree = {}

for _ in range(n):
    data, left_node, right_node = input().split()
    
    tree[data] = Node(data, left_node, right_node)

pre_order(tree['A'])
print()
in_order(tree['A'])
print()
post_order(tree['A'])