[트리] 백준 1991 파이썬 (트리 순회) 실버1

-풀이

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 _ 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'])

-풀이 설명

[30분 no sol] 전위 순회는 DFS랑 비슷한 느낌이라서 DFS로 풀면되나 싶었는데 중위, 후위 구하는 법이 생각이 안나서 풀이를보게 되었다. 이 문제는 트리를 이용해 푸는 것이었다. 트리를 한 번도 풀어본 적이 없었는데 트리를 처음 배우게 된 계기가 되었다. 풀이 방법은 def함수로 출력값의 위치를 조절하여 전위, 중위, 후위로 나누어 함수를 차례대로 실행하면 되었다. 하지만 아직은 tree[node] = Node(item=node, left=left, right=right) 이 코드와 맨 위 클래스 Node코드가 잘 이해가 가지 않아서 트리에 대해 좀 더 자세히 알아봐야겠다.

출처 : https://jjangsungwon.tistory.com/12

2022/01/06 오전 1:38 복습 + 이해 완료

#전위(루트->왼->오)

def pre(node):

  if node != '.':

    print(node, end='')

    pre(dic[node][0])

    pre(dic[node][1])

#중위(왼쪽->루트->오른쪽)

def mid(node):

  if node != '.':

    mid(dic[node][0])

    print(node, end='')

    mid(dic[node][1])

#후위(왼쪽->오른쪽->루트)

def after(node):

  if node != '.':

    after(dic[node][0])

    after(dic[node][1])

    print(node, end='')

#노드 개수

N = int(input())

#딕셔너리(키:루트, 벨류:왼쪽, 오른쪽 자식)

dic = {}

for i in range(N):

  root, left, right = input().split()

  dic[root] = [left, right]

pre('A')

print()

mid('A')

print()

after('A')