•
문제
이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 프로그램을 작성하시오.
예를 들어 위와 같은 이진 트리가 입력되면,
•
전위 순회한 결과 : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 자식)
•
중위 순회한 결과 : DBAECFG // (왼쪽 자식) (루트) (오른쪽 자식)
•
후위 순회한 결과 : DBEGFCA // (왼쪽 자식) (오른쪽 자식) (루트)
가 된다.
풀이
•
기본 알고리즘
1. 입력 받을 때 A,B,C,,, 대신 0,1,2,,, 형태로 입력받는다.
2. A~Z 까지 해당하는 배열에 left , right 쌍으로 자식을 붙여준다.
3. 순회 종류에 따라서 dfs 알고리즘을 통해 탐색 후 출력한다.
Python
복사
•
Traversal 함수
- start : 순회의 시작점
def preorder(start): # 좌 -> 중단 -> 우 순서
print(chr(start + 65), end ='') # 0,1,2로 저장했으니 출력할땐 다시 A,B,C로
if arr[start][0] != -19: # 자식이 없는 경우(. 인 경우)
preorder(arr[start][0])
if arr[start][1] != -19:
preorder(arr[start][1])
def inorder(start): # 중단 -> 좌 -> 우 순서
if arr[start][0] != -19:
inorder(arr[start][0])
print(chr(start + 65), end ='')
if arr[start][1] != -19:
inorder(arr[start][1])
def postorder(start): # 좌 -> 우 -> 중단 순서
if arr[start][0] != -19:
postorder(arr[start][0])
if arr[start][1] != -19:
postorder(arr[start][1])
print(chr(start + 65), end ='')
Python
복사
•
Main 함수 동작
for i in range(n):
root, left, right = input().split()
arr[ord(root) - 65].append(ord(left) - 65) #왼쪽 자식
arr[ord(root) - 65].append(ord(right) - 65) #오른쪽 자식
preorder(0)
print()
inorder(0)
print()
postorder(0)
Python
복사
다른 풀이(Class를 통한 Node 구현)
class Node:
def __init__(self, data, left_node, right_node):
self.data = data
self.left_node = left_node
self.right_node = right_node
def pre_order(node):
print(node.data, end='')
if node.left_node != '.':
pre_order(tree[node.left_node])
if node.right_node != '.':
pre_order(tree[node.right_node])
def in_order(node):
if node.left_node != '.':
in_order(tree[node.left_node])
print(node.data, end='')
if node.right_node != '.':
in_order(tree[node.right_node])
def post_order(node):
if node.left_node != '.':
post_order(tree[node.left_node])
if node.right_node != '.':
post_order(tree[node.right_node])
print(node.data, end='')
n = int(input())
tree = {}
for i in range(n):
data, left_node, right_node = input().split()
tree[data] = Node(data, left_node, right_node)
pre_order(tree['A'])
print()
in_order(tree['A'])
print()
post_order(tree['A'])
Python
복사
중요
1.
C++ 에서 char - '0' 을 통해 ASCII Char 변형시키는 것과 같이 파이썬에서는 ord와 chr를 통해 변형시킨다.
Char 변형시키는 것과 같이 파이썬에서는 ord와 chr를 통해 변형시킨다.print(ord(char) - 65)
print(chr(start + 65))
Python
복사
2. Tree를 구현하는 경우에 dictionary를 사용하여 구현하는 방법이 많이 쓰인다. 기억하자!
tree = {}
for i in range(n):
data, left_node, right_node = input().split()
tree[data] = Node(data, left_node, right_node)
Python
복사
