트리 : 트리 순회(백준 1991번)

▶ 문제 : https://www.acmicpc.net/problem/1991

1991번: 트리 순회

##### 문제 #####
# 이진 트리를 입력받아 
# 전위 순회(preorder traversal), 
# 중위 순회(inorder traversal), 
# 후위 순회(postorder traversal) 
# 결과를 출력하는 프로그램을 작성하시오.

##### 입력 #####
# 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 
# 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 
# 노드의 이름은 A부터 차례대로 알파벳 대문자로 매겨지며, 
# 항상 A가 루트 노드가 된다. 자식 노드가 없는 경우에는 .으로 표현한다.

##### 출력 #####
# 첫째 줄에 전위 순회, 둘째 줄에 중위 순회, 셋째 줄에 후위 순회한 결과를 출력한다. 
# 각 줄에 N개의 알파벳을 공백 없이 출력하면 된다.

 

▶ 접근 방법

우선, 문제에도 간단히 나와있지만 트리 순회와 관련한 개념을 이해할 필요가 있었다. 
트리 순회에 대해서는 아래 관련 링크 중 BFS에 정리해두었다.

문제 해결을 위해서 가장 먼저 트리의 노드 클래스를 만들었다.
그리고 주어진 입력 값과 해당 노드 클래스를 이용하여 개별 노드들을 생성하였다.
이때 개별 노드들은 딕셔너리에 담아주었다. 
이후, 전위-중위-후위 순회에 해당하는 함수들을 각각 만들었다.
이때 개별 함수 내부는 순회 별 특징에 맞추어 재귀 함수로 구현하였다.

 

▶ 풀이 코드

import sys

class Node :
    def __init__(self, value, left, right):
        self.value = value
        self.left = left
        self.right = right
    
tree = {}

for _ in range(int(input())): 
    value, left, right  = list(sys.stdin.readline().split())
    tree[value] = Node(value, left, right)

# for i in tree :
#     print(f'tree_{i}의 left는 {tree[i].left}, right는 {tree[i].right} ')
    

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

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

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

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

 

▶ 관련 링크

2021.11.18 - [알고리즘] - 트리(Tree)란?

2021.11.18 - [알고리즘] - BFS(Breadth First Search, 너비 우선 검색)이란?

2021.11.18 - [알고리즘] - DFS(Depth First Search, 깊이 우선 탐색)이란?

2021.11.19 - [알고리즘] - 그래프(Graph)란?