[Python/백준] 1991번: 트리 순회

문제

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

1991번: 트리 순회

---

문제 요약

이진 트리를 입력 받고, 전위 순회, 중위 순회, 후위 순회한 결과를 출력한다.

 

+ 노드의 이름은 A부터 차례대로 알파벳 대문자로 매겨지며, 항상 A가 루트 노드가 된다.

 

+ 자식 노드가 없는 경우에는 .으로 표현한다.

---

코드

import sys

input = sys.stdin.readline

def preorder(root): # 전위 순회
    if root != '.':
        print(root, end = '') # root 노드 출력
        preorder(tree[root][0]) # left 자식 노드를 root로 탐색
        preorder(tree[root][1]) # right 자식 노드를 root로 탐색

def inorder(root): # 중위 순회
    if root != '.':
        inorder(tree[root][0]) # left 자식 노드를 root로 탐색
        print(root, end = '') # root 노드 출력
        inorder(tree[root][1]) # right 자식 노드를 root로 탐색

def postorder(root): # 후위 순회
    if root != '.':
        postorder(tree[root][0]) # left 자식 노드를 root로 탐색
        postorder(tree[root][1]) # right 자식 노드를 root로 탐색
        print(root, end = '') # root 노드 출력

N = int(input()) # 입력 받을 이진 노드의 개수

tree = {} 
# 트리 딕셔너리
# key: 루트 노드, value: key의 자식 노드들 [좌, 우]

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

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

---

코드 설명

1. 입력 받은 노드를 key값으로, 그 노드의 자식 노드를 value값으로 갖는 딕셔너리 tree를 생성한다.

 

2. 재귀를 이용하여 preorder(전위 순회), inorder(중위 순회), postorder(후위 순회) 별 출력을 진행하는 함수를 생성한다. 

 

+ 전위 순회: root부터 시작하여 뿌리 방문 => 왼쪽 자식 노드 방문 => 오른쪽 자식 노드 방문

+ 중위 순회: root부터 시작하여 왼쪽 자식 노드 방문 => 뿌리 방문 => 오른쪽 자식 노드 방문

+ 후위 순회: root부터 시작하여 왼쪽 자식 노드 방문 => 오른쪽 자식 노드 방문 => 뿌리 방문