# 아래 ref 참조코드
# 한번 재귀할 때마다 탐색을 한번 더 하는 의미로 받아들이자
# 함수 안의 ~~order(tree[root][0]) 재귀함수는 왼쪽으로 끝까지 탐색한다는 의미
# 함수 안의 ~~order(tree[root][1]) 재귀함수는 오른쪽으로 끝까지 탐색한다는 의미
# root -> 출력하면 됨
# 1. 전위 순회 : 루트 -> 왼쪽 자식 -> 오른쪽 자식이므로 재귀함수 순서도 root출력문 -> 왼쪽 재귀함수 -> 오른쪽 재귀함수
def preorder(root): # 루트 -> 왼쪽 자식 -> 오른쪽 자식 순으로 탐색
if root != '.':
print(root, end='') # root
preorder(tree[root][0]) # left -> left가 새로운 root가 된다.
preorder(tree[root][1]) # right -> right가 새로운 root가 된다.
# 2. 중위 순회 : 왼쪽 자식 -> 루트 -> 오른쪽 자식이므로 재귀함수 순서도 왼쪽 재귀함수 -> root 출력문 -> 오른쪽 재귀함수
def inorder(root): # 왼쪽 자식 -> 루트 -> 오른쪽 자식 순으로 탐색
if root != '.':
# TEST CASE를 예로 들면 B에서 tree[root][0] = "D"이고 D의 tree(root[0]) = "."이 돼서 root인 D를 출력하고 right로 넘어간다.
inorder(tree[root][0]) # left
print(root, end='') # root
inorder(tree[root][1]) # right
# 3. 후위 순회 : 왼쪽 자식 -> 오른쪽 자식 -> 루트이므로 재귀함수 순서도 왼쪽 재귀함수 -> 오른쪽 재귀함수 -> root 출력문
def postorder(root): # 왼쪽 자식 -> 오른쪽 자식 -> 루트 순으로 탐색
if root != '.':
postorder(tree[root][0]) # left
postorder(tree[root][1]) # right
print(root, end='') # root
처음 root 값에 "A"가 들어왔을 때 tree에서 만들어 뒀던 하위 노드 값을 불러옴.
14라인에서 "A"를 출력하고 15라인에서 " A " 의 노드가 "b", "c" 두 개 인데 먼저 "B"부터 호출함
"B"가 호출이 되고 이후에 위와 똑같이 15라인에서 "B"의 하위노드 "D"를 호출함
현재 D의 하위 노드는 'D': ('.', '.') 둘 다 없다.
" preorder(tree[root][0]) # left " 함수가 동작중인 상황에서 입력값으로 "." 이 들어와서 Return value "None"으로 탈출한다. 이후 preorder(tree[root][1]) # righ 값 또한 위와 같은 상황으로 탈출하게 된다.
이로써 "D"로 매개변수를 받은 함수는 재귀적으로 자동 탈출하게 된다.
트리 'B': ('D', '.') 상황
직전에 "B"의 좌측 노드 "D"를 탈출하였기 때문에 B의 우측노드"."이 입력으로 받았다 이 또한 해당사항이 없으므로 Return value는 none으로 탈출된다.
좌측은 탐색이 끝났으므로 원래 A 우측 탐색이 시작된다. 'A': ('B', 'C')
좌측부터 반복해서 확인을 한 후 "E" 또한 None을 만나 함수를 탈출하고 다음 함수 즉 우측 하위 노드 탐색을 하며 둘 다 None이므로 "E"또한 마무리된다.
이후 F-> 좌측 노드는 None, 이므로 바로 탈출해서 우측 노드 G로 재귀적으로 다시 받아 탐색 후 차례차례 회수되며 끝이난다.
import sys
N = int(sys.stdin.readline().strip())
tree = {}
for n in range(N):
root, left, right = sys.stdin.readline().strip().split()
tree[root] = [left, right]
def preorder(root):
if root != '.':
print(root, end='') # root
preorder(tree[root][0]) # left
preorder(tree[root][1]) # right
def inorder(root):
if root != '.':
inorder(tree[root][0]) # left
print(root, end='') # root
inorder(tree[root][1]) # right
def postorder(root):
if root != '.':
postorder(tree[root][0]) # left
postorder(tree[root][1]) # right
print(root, end='') # root
preorder('A')
print()
inorder('A')
print()
postorder('A')
