[Algorithm] 트리의 순회(Tree Traversal)

 

안녕하세요! 공대남입니다.

오늘은 트리의 순회구조인 전위순회, 중위 순회, 후위 순회을 알아보겠습니다.

 

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 = {}

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']) #전위순회

in_order(tree['A']) #중위순회

post_order(tree['A']) #후위순회