https://www.acmicpc.net/problem/1991
1991번: 트리 순회
첫째 줄에는 이진 트리의 노드의 개수 N(1≤N≤26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 영문자
www.acmicpc.net
풀이
class Node:
def __init__(self, item, left, right):
self.item=item
self.left=left
self.right=right
def preorder(node):
print(node.item, 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.item, 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.item, end='')
if __name__=="__main__":
N=int(input())
tree={}
for i in range(N):
node, left, right=map(str, input().split())
tree[node]=Node(item=node, left=left, right=right)
preorder(tree['A'])
print()
inorder(tree['A'])
print()
postorder(tree['A'])
-dictionary 활용
Node 클래스를 활용하여 tree dictionary에 왼쪽 자식과 오른쪽 자식 그리고 루트를 등록해둠
{'A':('B','C')} -->A의 자식들을 표현
tree[node]=Node(item=node, left=left, right=right)
이런 식으로 트리를 표현
-order 함수
if node.left!=".":
--order(tree[node.left])
if node.right!=".":
--order(tree[node.right])
자식이 비어 있지 않다면 재귀로 넘김
전위, 중위, 후위에 따라서 print의 위치를 옮겨서 처리함
백준 2493 탑 python (0) | 2021.09.06 |
---|---|
백준 9935 문자열폭발 python (0) | 2021.09.02 |
Boj 15828 Router python (0) | 2021.07.23 |
Boj 큐2 python (0) | 2021.07.23 |
Boj 9012 괄호 python (0) | 2021.07.22 |
댓글 영역