📖문제
이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 프로그램을 작성하시오.
예를 들어 위와 같은 이진 트리가 입력되면,
- 전위 순회한 결과 : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 자식)
- 중위 순회한 결과 : DBAECFG // (왼쪽 자식) (루트) (오른쪽 자식)
- 후위 순회한 결과 : DBEGFCA // (왼쪽 자식) (오른쪽 자식) (루트)
가 된다.
⌨️입력
첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파벳 대문자로 매겨지며, 항상 A가 루트 노드가 된다. 자식 노드가 없는 경우에는 .으로 표현한다.
🖨️출력
첫째 줄에 전위 순회, 둘째 줄에 중위 순회, 셋째 줄에 후위 순회한 결과를 출력한다. 각 줄에 N개의 알파벳을 공백 없이 출력하면 된다.
예제 입력
7
A B C
B D .
C E F
E . .
F . G
D . .
G . .예제 출력
ABDCEFG
DBAECFG
DBEGFCA🖥️코드
#입력 받기
import sys #표준 입력을 읽기위한 모듈
N = int(sys.stdin.readline()) #N은 tree의 노드 수
tree = {} #left와 right 두 가지 노드 정보를 저장하기 위해 딕셔너리 사용
"""
sys 안 쓸 때 코드
N= int(input())
tree = {}
"""
#N 반복하며 딕셔너리에 저장
for _ in range(N): #_는 밑에 for문의 i를 사용하지 않기 때문에 빈칸처리 해주는 것
root, left, right = sys.stdin.readline().strip().split()
#패킹, 언패킹
#root = node_str[0]
#left = node_str[1]
#right = node_str[2]
tree[root] = [left, right]
#preorder root->left->right
def preorder(root):
if root !='.': #'.'이면 그냥 지나가세요
#if node == ".":
# return
#이렇게 탈출 조건 적으면 밑에 들여쓰기 안 해도 됨. 더 좋은 코드!
print(root, end='') #root #줄 바꾸지마 end=''
preorder(tree[root][0]) #left
preorder(tree[root][1]) #right
#계속 순회해야 하기 때문에 preorder로 감싼다
#inorder left -> root -> right
def inorder(root):
if root !='.':
inorder(tree[root][0]) #left
print(root, end='') #root
inorder(tree[root][1]) #right
#postorder left -> right -> root
def postorder(root):
if root !='.':
postorder(tree[root][0]) #left
postorder(tree[root][1]) #right
print(root, end='') #root
#출력
preorder('A') #A는 루트
print() #end = ''처리 해놨기 때문에 줄바꿈 코드 적어줘야 함
inorder('A')
print()
postorder('A')