[Python] 백준 1991 트리 순회

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

1991번: 트리 순회

 

문제 해결

https://www.acmicpc.net/problem/1991 이미지 참조

	전위 순회(preorder)	중위 순회(inorder)	후위 순회(postorder)
스캔 순서	노드 방문→왼쪽 자식→오른쪽 자식	왼쪽 자식→노드방문→오른쪽 자식	왼쪽 자식→오른쪽 자식 →노드 방문
예시	A→B→D→C→E→F→G	D→B→A→E→C→F→G	D→B→E→G→F→C→A

위 내용을 잘 모르겠으면 자료구조(Data Structure)의 트리 부분을 공부하고 오는 것이 좋다.

 

- 이 트리문제는 부모-자식 관계가 매우 중요하다. 그리고 부모는 자식(?)이 최대 2개이다. 따라서 딕셔너리(dictionary)를 이용하여 tree= dict() 로 정의하여 tree[parent]=[left_child,right_child] 로 정리하는 것이 깔끔할 것이다. 

- 자식이 없을 때는 '.'를 쓰는데 '.'를 구별하는 방법이나 조건이 필요할 것이다. '.'을 출력하지 않기 위해서 if parent != '.' 조건을 이용하는 것이 깔금할 것이다.

 

풀이

import sys
input = sys.stdin.readline

def preorder(tree:dict, present:str):
    if present != '.':
        print(present, end='') # present
        preorder(tree, tree[present][0]) # left_child
        preorder(tree, tree[present][1]) # right_child

def inorder(tree:dict, present:str):
    if present != '.':
        inorder(tree, tree[present][0])
        print(present, end='')
        inorder(tree, tree[present][1])        
def postorder(tree:dict, present:str):
    if present != '.':
        postorder(tree, tree[present][0])
        postorder(tree, tree[present][1])
        print(present, end='')
if __name__=="__main__":
    n = int(input())
    tree = dict()
    for _ in range(n):
        present, left, right = map(str,input().strip().split())
        tree[present] = [left, right]

    preorder(tree, 'A')
    print()
    inorder(tree, 'A')
    print()
    postorder(tree, 'A')