[백준] 트리 순회

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

1991번: 트리 순회

트리 자료구조를 구현하고, 알맞게 순회할수 있게 해야하는 문제입니다.

 

우선 문제부터 간단하게 요약하면, 

Tree의 정보가 들어오면, 이 Tree의 Preorder, Inorder, Postorder traversal 결과를 알맞게 return해야 합니다.

 

<Solution>

Node라는 class를 만들어서 이 자료구조를 관리해주는 형태로 진행하면 됩니다. 

class node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

각각의 traversal은 알맞게 재귀함수로 구현하였습니다.

 

실제 구현은 아래와 같습니다. 

import sys
import string
from collections import defaultdict

N = int(sys.stdin.readline().rstrip())

class node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

alphabet_string = string.ascii_uppercase
alphabet_list = list(alphabet_string)

fast_search_dict = defaultdict(int)
for idx, alp in enumerate(alphabet_list):
    fast_search_dict[alp] = idx

nodes = []
# make 26 node and save
for i in range(26):
    node_ = node(alphabet_list[i])
    nodes.append(node_)

for _ in range(N):
    nd, left, right = sys.stdin.readline().rstrip().split()
    node__ = nodes[fast_search_dict[nd]]
    if left != '.':
        node__.left = nodes[fast_search_dict[left]]
    if right != '.':
        node__.right = nodes[fast_search_dict[right]]

def preorder(node, return_list = []):
    if node:
        return_list.append(node.data)
        preorder(node.left, return_list)
        preorder(node.right, return_list)
    
    return return_list

def inorder(node, return_list = []):
    if node:
        inorder(node.left, return_list)
        return_list.append(node.data)
        inorder(node.right, return_list)

    return return_list

def postorder(node, return_list = []):
    if node:
        postorder(node.left, return_list)
        postorder(node.right, return_list)
        return_list.append(node.data)

    return return_list

print(''.join(preorder(nodes[0])))
print(''.join(inorder(nodes[0])))
print(''.join(postorder(nodes[0])))