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

✅문제: 1991번

📌문제풀이

이 문제는 주어진 이진 트리를 전위 순회(Preorder), 중위 순회(Inorder), 후위 순회(Postorder) 방식으로 탐색한 결과를 출력하는 문제임. 각 순회 방식의 차이를 이해하고, 이를 구현하는 연습을 할 수 있음.

1. 트리 구성
   • 입력으로 주어진 노드 정보(루트, 왼쪽 자식, 오른쪽 자식)를 바탕으로 트리를 생성.
   • 각 노드를 Node 객체로 표현하며, 딕셔너리 tree를 사용해 트리 구조를 저장.
2. 순회 방식 구현
   • 전위 순회 (Preorder):
     • 순서: 루트 → 왼쪽 자식 → 오른쪽 자식.
     • 루트를 먼저 방문하고, 왼쪽과 오른쪽 자식을 재귀적으로 방문.
   • 중위 순회 (Inorder):
     • 순서: 왼쪽 자식 → 루트 → 오른쪽 자식.
     • 왼쪽 자식을 먼저 방문한 후, 루트를 방문하고 오른쪽 자식을 재귀적으로 방문.
   • 후위 순회 (Postorder):
     • 순서: 왼쪽 자식 → 오른쪽 자식 → 루트.
     • 왼쪽과 오른쪽 자식을 모두 방문한 후, 루트를 방문.
3. 결과 출력
   • 각 순회 방식의 결과를 출력.

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

def preorder(node):
    print(node.data, end='')
    if node.left != '.': preorder(tree[node.left])
    if node.right != '.': preorder(tree[node.right])

def inorder(node):
    if node.left != '.': inorder(tree[node.left])
    print(node.data, end='')
    if node.right != '.': inorder(tree[node.right])

def postorder(node):
    if node.left != '.': postorder(tree[node.left])
    if node.right != '.': postorder(tree[node.right])
    print(node.data, end='')

n = int(input())  # 노드의 개수
tree = {}

for _ in range(n):
    root, left, right = input().split()
    tree[root] = Node(root, left, right)

preorder(tree['A'])
print()
inorder(tree['A'])
print()
postorder(tree['A'])

예제에 대해서 트리를 구성하고 차례대로 진행하면 아래와 같았음.

# 예제 입력 1
7
A B C
B D .
C E F
E . .
F . G
D . .
G . .

위 입력은 아래 트리 구조를 의미함.

 

# 트리 구조
     A
    / \
   B   C
  /   / \
 D   E   F
            \
             G

• 순회 방식 결과
  • 전위 순회 (Preorder):
    • 루트 → 왼쪽 자식 → 오른쪽 자식
    • A B D C E F G
  • 중위 순회 (Inorder):
    • 왼쪽 자식 → 루트 → 오른쪽 자식
    • D B A E C F G
  • 후위 순회 (Postorder):
    • 왼쪽 자식 → 오른쪽 자식 → 루트
    • D B E G F C A

 

# 예제 출력 1
ABDCEFG
DBAECFG
DBEGFCA

📌후기

• 트리의 순회 방식을 알고 있으면 그것을바탕으로 재귀적으로 구현하면 되는 문제였음.
• 머릿속으로 아는 지식을 실제 구현하는 것이 어려운 것 같음.