트리 순회 알고리즘의 종류

1. 전위 순회(Pre-Order Traverse)
2. 중위 순회(In-Order Traverse)
3. 후위 순회(Post-Order Traverse)
4. 단계 순회(Level-Order Traverse)

1. 전위 순회(Pre-Order Traverse)

• 전위 순회는 루트 노드를 만저 탐색하고
  이진 트리에서 왼쪽에 있는 노드부터 방문한다는 의미

방문 순서

• A -> B -> C -> D -> E -> F -> G

2. 중위 순회(In-Order Traverse)

• 왼쪽 자식 노드를 탐색하고, 루트 노드를 탐색, 오른쪽 자식 노드를 탐색 하는 방식

방문순서

• C-> B -> D -> A -> F -> E -> G

3. 후위 순회(Post-Order Traverse)

• 왼쪽 자식노드를 탐색하고, 오른쪽 자식 노드, 루트 노드를 탐색하는 방식

방문순서

• C -> D -> B -> F -> G -> E -> A

4. 단계 순회(Level-Order Traverse)

• 레벨 별로 차례대로 방문하는 순서

방문순서

• A -> B -> E -> C -> D -> F -> G

---

트리 순회 구현하기

                                          A
                                          
                                       B     C
                                     
                                   D    E   F    G

트리 구조에서 사용할 노드에 대한 자료형

class Node:
	def __init__(self, data):
    	self.data = data
        self.left = None
        self.right = None

노드 생성 및 이진트리 형태를 갖도록 초기화

def init_tree():
    global root
    
    new_node = Node("A")
    root = new_node
    new_node = Node("B")
    root.left = new_node
    new_node = Node("C")
    root.right = new_node
    new_node_1 = Node("D")
    new_node_2 = Node("E")
    node = root.left
    node.left = new_node_1
    node.right = new_node_2
    
    new_node_1 = Node("F")
    new_node_2 = Node("G")
    node = root.right
    node.left = new_node_1
    node.right = new_node_2

1. 전위순회(Pre-Order Traverse) 알고리즘 구현

• 트리 구조를 순회하기 위해 반드시 지켜야 할 기본적인 규칙 "노드는 오직 한번만 방문한다"

                                          A
                                          
                                       B     C
                                     
                                   D    E   F    G

• 루트 노드 먼저 탐색, 왼쪽에 있는 노드부터 방문하고, 다음 오른쪽 노드를 방문하는 방법

def preorder_traverse(node):
	if node == None: return
    print(node.data, end=" -> ") # 루트 노드 방문
    preorder_traverse(node.left) # 왼쪽 노드
    preorder_traverse(node.right) # 오른쪽 노드

• 재귀 호출 사용
• 콜 스택을 생각하면
  루트 노드에서 왼쪽 노드로 계속해서 쌓여 있는 상태로
  왼쪽 노드가 None이 될때까지 계속 쌓이면서 순회 하는 구조

순회 결과

• A -> B -> D -> E -> C -> F -> G

2. 중위 순회(In-Order Traverse) 알고리즘

• 왼쪽 자식 노드를 방문하고 그 다음 부모노드를 방문한 후 다시 오른쪽 자식 노드를 방문

                                          A
                                          
                                       B     C
                                     
                                   D    E   F    G

def inorder_traverse(node):
    if node == None: return
    inorder_traverse(node.left) # 왼쪽노드로 쭉 내려감
    print(node.data, end=" -> ") # 왼쪽 노드가 None으로 리턴 받은 다음 출력
    inorder_traverse(node.right) # 오른쪽 노드가 스택에 쌓임

• 재귀 호출 사용
• 콜 스택을 생각해보면
  왼쪽 자식노드를 향해서 계속 콜스택이 쌓임
  왼쪽 자식 노드가 None이 되면 return 됨
  리턴 시점부터 데이터 출력, 다시 오른쪽 노드 호출

순회결과

• D -> B -> E -> A -> F-> C -> G

3. 후휘 순회(Post-Order Traverse)알고리즘

• 왼쪽 자식 노드를 방문하고 다음 오른쪽 자식노드를 방문한 후
  마지막으로 부모노들 방문하는 알고리즘

                                          A
                                          
                                       B     C
                                     
                                   D    E   F    G

def postorder_traverse(node):
    if node == None: return
    postorder_traverse(node.left)
    postorder_traverse(node.right)
    print(node.data, end=" -> ")

순회 결과

• D -> E -> B -> F -> G -> C -> A

4. 단계 순회(Level-Order Traverse)알고리즘

• 루트 노드 부터 level순서대로 왼쪽부터 오른쪽으로 방문하는 순회 알고리즘

                                          A
                                          
                                       B     C
                                     
                                   D    E   F    G

• 단계 순회 알고리즘의 경우 스택을 사용하기 어렵고, 큐를 사용하는 것이 더 바람직함

levelq = []

def levelorder_traverse(node):
    global levelq
    levelg.append(node)
    
    
    while len(levelq) != 0:
        # visit
        visit_node = levelq.pop(0)
        print(visit_node.data, end =" -> ")
        # childput
        if visit_node.left != None:
            levelq.append(visit_node.left)
        if visit_node.right != None:
            levelq.append(visit_node.right)
            

• 매개 변수로 받은 현재 노드를 큐인 levelq에 저장
• 큐의 크기가 0이 아니라면 큐에서 항목을 하나씩 가져와서 그 항목의 데이터를 출력
• 현재 방문한 노드를 visit_node라고하고,
  visit_node의 왼쪽 노드가 존재하면 큐에 visit_node의 왼쪽 노드를 삽입하고,
  오른쪽 노드가 존재하는 지를 검사
• 오른쪽 노드가 존재하면 큐에 저장하고 반복문 실행

  class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
        
def init_tree():
    global root
    
    new_node = Node("A")
    root = new_node
    new_node = Node("B")
    root.left = new_node
    new_node = Node("C")
    root.right = new_node
    new_node_1 = Node("D")
    new_node_2 = Node("E")
    node = root.left
    node.left = new_node_1
    node.right = new_node_2
    
    new_node_1 = Node("F")
    new_node_2 = Node("G")
    node = root.right
    node.left = new_node_1
    node.right = new_node_2

# 전위 순회
def preorder_traverse(node):
    if node == None: return
    print(node.data, end= ' -> ')
    preorder_traverse(node.left)
    preorder_traverse(node.right)

# 중위 순회    
def inorder_traverse(node):
    if node == None: return
    inorder_traverse(node.left)
    print(node.data, end=" -> ")
    inorder_traverse(node.right)
    
    
# 후위 순회    
def postorder_traverse(node):
    if node == None: return
    postorder_traverse(node.left)
    postorder_traverse(node.right)
    print(node.data, end=" -> ")
    
levelq = []

def levelorder_traverse(node):
    global levelq
    levelq.append(node)
    
    
    while len(levelq) != 0:
        # visit
        visit_node = levelq.pop(0)
        print(visit_node.data, end =" -> ")
        # childput
        if visit_node.left != None:
            levelq.append(visit_node.left)
        if visit_node.right != None:
            levelq.append(visit_node.right)
            
    
    
    
    
if __name__ == "__main__":
    init_tree()
    print("전위 순회")
    preorder_traverse(root)
    print()
    
    print("중위 순회")
    inorder_traverse(root)
    print()
    
    print("후위 순회")
    postorder_traverse(root)
    print()
    
    print("단계 순회")
    levelorder_traverse(root)
    print()
    ```
    
전위 순회
A -> B -> D -> E -> C -> F -> G -> 
중위 순회
D -> B -> E -> A -> F -> C -> G -> 
후위 순회
D -> E -> B -> F -> G -> C -> A -> 
단계 순회
A -> B -> C -> D -> E -> F -> G ->