트리의 순회(Tree Traversal)
트리 자료구조에 포함된 노드를 특정한 방법으로 한번씩 방문하는 방법이다.
트리의 정보를 시각적으로 확인할 수 있다.
대표적인 트리 순회 방법은 다음과 같다.
- 전위 순회(pre-order traverse)
- 중위 순회(in-order traverse)
- 후위 순회(post-order traverse)
트리 순회 예시
전위 순회(pre-order traverse): 루트를 먼저 방문한다.
👉 A → B → D → E → C → F → G
중위 순회(in-order traverse): 왼쪽 자식을 방문한 뒤에 루트를 방문한다.
👉 D → B → E → A → F → C → G
후위 순회(post-order traverse): 오른쪽 자식을 방문한 뒤에 루트를 방문한다.
👉 D → E → B → F → G → C → A
트리 순회 구현하기
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 != None: # 왼쪽 노드 방문,
pre_order(tree[node.left_node])
if node.right_node != None: # 오른쪽 노드 방문
pre_order(tree[node.right_node])
# 중위 순회
def in_order(node):
if node.left_node != None: # 왼쪽 노드 먼저 방문
in_order(tree[node.left_node])
print(node.data, end = ' ') # 자신의 데이터 출력 후
if node.right_node != None: # 오른쪽 노드 방문
in_order(tree[node.right_node])
# 후위 순회
def post_order(node):
if node.left_node != None: # 왼쪽 노드 방문,
post_order(tree[node.left_node])
if node.right_node != None: # 오른쪽 노드 방문 후에
post_order(tree[node.right_node])
print(node.data, end = ' ') # 자신의 데이터 출력
n = int(input())
tree = {}
# tree 데이터 삽입
for i in range(n):
data, left_node, right_node = input().split()
if left_node == "None":
left_node = None
if right_node == "None":
right_node = None
tree[data] = Node(data, left_node, right_node)
# 트리 순회
pre_order(tree['A'])
print()
in_order(tree['A'])
print()
post_order(tree['A'])
# Input 예시
# 7
# A B C
# B D E
# C F G
# D None None
# E None None
# F None None
# G None None
# 출력 결과
# A B D E C F G
# D E B F G C A
# D B E A F C G
참조
코딩 테스트를 위한 트리(Tree) 자료구조 10분 핵심 요약
https://www.youtube.com/watch?v=i5yHkP1jQmo
Uploaded by N2T
