트리 순회

 트리 순회란 그래프 순회의 한 형태로 트리 자료구조에서 각 노드를 정확히 한 번 방문하는 과정을 말한다.

 

 그래프 순회와 마찬가지로 트리 순회 또한 DFS 또는 BFS로 탐색하는데, 특히 이진트리에서 DFS는 노드의 방문 순서에 따라 다음과 같이 크게 3가지 방식으로 구분된다.

 

 1. 전위 순회(preorder) - NLR

 2. 중위 순회(inorder) - LNR

 3. 후위 순회(post-order) - LRN

 

 L = 현재 노드의 왼쪽 서브트리

 R = 현재 노드의 오른쪽 서브트리

 N = 현재 노드 자신

 

class Node:
    def __init__(self,val,left=None,right=None):
        self.val=val
        self.left=left
        self.right=right
        
root=Node('F',Node('B',Node('A'),Node('D',Node('C'),Node('E'))),
          Node('G',None,Node('I',Node('H')))
          )

def preorder(node):  # 전위순회
    if node is None:
        return 
    
    print(node.val,end=' ')
    preorder(node.left)
    preorder(node.right)
    
preorder(root)
print('\n')

def inorder(node):  # 중위 순회
    if node is None:
        return 
    inorder(node.left)
    print(node.val,end=' ')
    inorder(node.right)
    
inorder(root)
print('\n')

def postorder(node): # 후위 순회
    if node is None:
        return 
    postorder(node.left)
    postorder(node.right)
    print(node.val,end=' ')
    
postorder(root)
print('\n')