백준 1991(트리 순회) - Python(파이썬) - 트리,재귀

1991번: 트리 순회

문제 설명 

  전위 순회의 경우 , 루트 -> 왼쪽 -> 오른쪽

  중위 순회의 경우, 왼쪽 -> 루트 -> 오른쪽

  후회 순회의 경우, 왼쪽 -> 오른쪽 -> 루트

tree[루트] = [ 왼쪽, 오른쪽 ] 

  tree[A] = [ B,C ]

  tree[B] = [ D ]

  tree[C] = [ E,F ]

  tree[E] = [ . , . ]

  tree[F] = [ . , G ] 

  tree[D] = [ . , . ] 

  tree[G] = [ . , . ]

Python에서는 trees는 디셔너리구조( 다른 언어에서는 HashMap 구조 )

tree =  {'A': ['B', 'C'], 'B': ['D', '.'], 'C': ['E', 'F'], 'E': ['.', '.'], 'F': ['.', 'G'], 'D': ['.', '.'], 'G': ['.', '.']} 

문제 풀이 ( 재귀 함수 호출 )
① 함수 만들 때 root값을 받아들이는 전위 함수, 중위 함수, 후위 함수 만들기
② 루트 값은 함수에서 주어졌으므로 root값은 그대로 출력, 왼쪽, 오른쪽 값은 재구함수 호출
  전위 순회의 경우 :
    루트 값은 제일 먼저 출력하고, 그 후에는 왼쪽값은 전위 순회 함수 호출, 오른쪽 값은 전위 순회 함수 호출
  중위 순회의 경우 :
    왼쪽 값은 중위 함수 호출하고, 루트 값 출력 , 오른쪽 값은 중위 함수 호출
  후위 순회의 경우 :
    왼쪽 값은 후위 순회 함수 호출하고, 오른쪽 값은 후위 함수 호출, 루트 값 출력
③ 단 , '.' 이 들어가므로 '.'인 경우에는 연산을 하지 않는다.

import sys
n = int(sys.stdin.readline())
#디셔너리
tree={}
for i in range(n):
    #루트,왼쪽, 오른쪽
    root,left,right=sys.stdin.readline().split()
    #디셔너리 생성
    tree[root]=[left,right]

#전위함수
def preorder(root):
    #'.'이 아닌 경우
    if root!='.':
        #ROOT -> 왼쪽 -> 오른쪽
        print(root, end="")
        #왼쪽값 preorder 
        preorder(tree[root][0])
        #오른쪽 값 preorder
        preorder(tree[root][1])
#중위 함수
def inorder(root):
    #'.'이 아닌 경우
    if root!='.':
        #왼쪽 -> 루트 -> 오른쪽
        inorder(tree[root][0])
        print(root,end="")
        inorder(tree[root][1])
#후위 함수
def postorder(root):
    if root!='.':
        #왼쪽 -> 오른쪽 -> 루트
        postorder(tree[root][0])
        postorder(tree[root][1])
        print(root,end="")

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