트리 순회 (백준 1991)

7 A B C B D . C E F E . . F . G D . . G . .

ABDCEFG DBAECFG DBEGFCA

import copy import sys sys.setrecursionlimit(10**9) N=int(input()) tree_dict = {} # dictionary 형태로 tree 제작 for _ in range(N): parent, left, right = input().split() tree_dict[parent] = [left, right, False] # [왼쪽 자식 노드, 오른쪽 자식 노드, is_left] # 'A'는 루트로 부모 노드 존재하지 않음 tree_dict['A'].append(None) # 부모 노드 추가 for i in tree_dict: left_c = tree_dict[i][0] right_c = tree_dict[i][1] if left_c != '.': tree_dict[left_c][2] = True tree_dict[left_c].append(i) if right_c != '.': tree_dict[right_c].append(i) # 중위 순회시에 tree의 정보가 바뀌기 때문에 후위 순회용으로 copy tree_dict2 = copy.deepcopy(tree_dict) # 전위 순회 def preorder(start, tree, print_list): print_list.append(start) # 루트 노드 프린트 if tree[start][0] != '.': # 만약 왼쪽 자식이 존재하면 preorder(tree[start][0], tree, print_list) # 내려감 if tree[start][1] != '.': # 왼쪽 자식들을 다 살펴본 후에 오른쪽 자식이 존재하면 preorder(tree[start][1], tree, print_list) # 내려감 # 중위 순회 def inorder(start, tree, print_list): if tree[start][0] != '.': # 만약 왼쪽 자식이 존재하면 inorder(tree[start][0], tree, print_list) # 내려감 else: # 왼쪽 자식이 없는 경우 print_list.append(start) # 루트 노드 프린트 if tree[start][1] != '.': # 만약 오른쪽 자식이 존재하면 inorder(tree[start][1], tree, print_list) # 내려감 if tree[start][2]: # 오른쪽을 다 살펴본 후에 만약 현재 루트 노드가 왼쪽 자식에 해당하면 tree[tree[start][3]][0] = '.' # 루트 노드의 부모 노드의 왼쪽 자식 노드를 지우고 inorder(tree[start][3], tree, print_list) # 부모 노드로 올라감 def postorder(start, tree, print_list): if tree[start][0] != '.': # 왼쪽 자식이 존재하면 postorder(tree[start][0], tree, print_list) # 내려감 elif tree[start][1] != '.': # 왼쪽 자식이 존재하지 않는데 오른쪽 자식이 존재하면 postorder(tree[start][1], tree, print_list) # 내려감 else: # 자식 노드가 존재하지 않으면 print_list.append(start) # 루트 노드 프린트 if tree[start][3] != None: # 만약 부모 노드가 존재하면 if tree[start][2]: # 루트 노드가 왼쪽 자식에 해당하는 경우 tree[tree[start][3]][0] = '.' # 루트 노드의 부모 노드의 왼쪽 자식을 지우고 postorder(tree[start][3], tree, print_list) # 부모 노드로 올라감 else: tree[tree[start][3]][1] = '.' # 오른쪽 자식에 해당하면 오른쪽 자식을 지우고 postorder(tree[start][3], tree, print_list) # 부모 노드로 올라감 pre_print_list = [] inorder_print_list = [] postorder_print_list = [] preorder('A', tree_dict, pre_print_list) inorder('A', tree_dict, inorder_print_list) postorder('A', tree_dict2, postorder_print_list) print(''.join(pre_print_list)) print(''.join(inorder_print_list)) print(''.join(postorder_print_list))