[백준] 1991번 트리 순회 (Python)

문제 주소

백준 1991번 트리 순회

1991번: 트리 순회

알고리즘

트리

힌트

전위 순회(preorder)

1. 노드를 방문한다.
2. 왼쪽 서브 트리를 전위 순회한다.
3. 오른쪽 서브 트리를 전위 순회한다.

중위 순회(Inorder)

1. 왼쪽 서브 트리를 중위 순회한다.
2. 노드를 방문한다.
3. 오른쪽 서브 트리를 중위 순회한다.

후위 순회(postorder)

1. 왼쪽 서브 트리를 후위 순회한다.
2. 오른쪽 서브 트리를 후위 순회한다.
3. 노드를 방문한다.

문제풀이

파이썬의 딕셔너리를 이용하여 트리를 구현할 수 있다.

 

class Node:
    def __init__(self, item, left=None, right=None):
      self.item = item
      self.left = left
      self.right = right
#풀이코드
def preorder(node): 
    print(node.item, end='')
    if node.left != None:
        preorder(tree[node.left])
    if node.right != None:
        preorder(tree[node.right])

def inorder(node):
    if node.left != None:
        inorder(tree[node.left])
    print(node.item, end='')
    if node.right != None:
        inorder(tree[node.right])

def postorder(node):
    if node.left != None:
        postorder(tree[node.left])
    if node.right != None:
        postorder(tree[node.right])
    print(node.item, end='')

n = int(input())
tree = {}
for i in range(n):
    a,b,c = input().split()
    if b == '.':
        b=None
    if c == '.':
        c=None
    tree[a] = Node(a,b,c)

preorder(tree['A'])
print()
inorder(tree['A'])
print()
postorder(tree['A'])

 백준 1991번 트리 순회