[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'

좋은 웹페이지 즐겨찾기