[BOJ] 1991 : 트리 순회
🔒 예제
>> 7
>> A B C
>> B D .
>> C E F
>> E . .
>> F . G
>> D . .
>> G . .
ABDCEFG
DBAECFG
DBEGFCA
🔧 풀이
1. 노드, 트리 구조 생성
1.1 노드 : 자기 자신, 좌우 노드 정보 포함
1.2 트리 : 딕셔너리 구조를 활용하여 트리 구조 표현
2. 전위, 중위, 후위순회 함수 생성 : 재귀함수 활용
2.1 전위순회 : L -> ROOT -> R
2.2 중위순회 : ROOT -> L -> R
2.3 후위순회 : L -> R -> ROOT
🔑 답안
import sys
class Node:
def __init__(self, data, left, right):
self.data = data
self.left = left
self.right = right
def preorder(node):
print(node.data, end="")
if node.left != '.':
preorder(tree[node.left])
if node.right != '.':
preorder(tree[node.right])
def inorder(node):
if node.left != '.':
inorder(tree[node.left])
print(node.data, end="")
if node.right != '.':
inorder(tree[node.right])
def postorder(node):
if node.left != '.':
postorder(tree[node.left])
if node.right != '.':
postorder(tree[node.right])
print(node.data, end="")
n = int(sys.stdin.readline().rstrip())
tree = {}
for _ in range(n):
node, left, right = map(str, sys.stdin.readline().split())
tree[node] = Node(data=node, left=left, right=right)
preorder(tree['A'])
print()
inorder(tree['A'])
print()
postorder(tree['A'])
💡 개념
### dictionary
dict = {}
dict['a'] = 'apple'
dict['b'] = 'baby'
print(dict['a']) # 'apple'
Author And Source
이 문제에 관하여([BOJ] 1991 : 트리 순회), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@ohhj1999/BOJ-1991-트리-순회저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)