Boj 1991 트리 순회 python

https://www.acmicpc.net/problem/1991

1991번: 트리 순회

---

풀이

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의 위치를 옮겨서 처리함