Problem Solving/Online Judge
[BOJ] #1991 - 트리 순회
se0m
2021. 6. 18. 15:43
1991번: 트리 순회
첫째 줄에는 이진 트리의 노드의 개수 N(1≤N≤26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 영문자
www.acmicpc.net
** 문제 유형
- 트리, 구현
** 풀이
- 전위 순회: 루트 -> 왼쪽 자식 -> 오른쪽 자식
- 중위 순회: 왼쪽 자식 -> 루트 -> 오른쪽 자식 <왼쪽부터 차례대로 출력>
- 후위 순회: 왼쪽 자식 -> 오른쪽 자식 -> 루트
class Node:
def __init__(self, data, left_node, right_node):
self.data = data
self.left_node = left_node
self.right_node = right_node
def pre_order(node): # 중 -> 왼 -> 오
print(node.data, end = '')
if node.left_node != '.':
pre_order(tree[node.left_node])
if node.right_node != '.':
pre_order(tree[node.right_node])
def in_order(node): # 왼 -> 중 -> 오
if node.left_node != '.':
in_order(tree[node.left_node])
print(node.data, end = '')
if node.right_node != '.':
in_order(tree[node.right_node])
def post_order(node): # 왼 -> 오 -> 중
if node.left_node != '.':
post_order(tree[node.left_node])
if node.right_node != '.':
post_order(tree[node.right_node])
print(node.data, end = '')
n = int(input())
tree = {}
for _ in range(n):
data, left_node, right_node = input().split()
tree[data] = Node(data, left_node, right_node)
pre_order(tree['A'])
print()
in_order(tree['A'])
print()
post_order(tree['A'])