[Tree] Queue를 이용한 레벨 순서 순회

레벨 순서 순회는 직관적이어서 쉽다. 과정을 나열하면 아래와 같다.

1. 루트부터 방문하고, 루트의 왼쪽과 오른쪽을 방문한다.
2. 루트 왼쪽 노드의 왼쪽과 오른쪽을 방문한다.
3. 루트 오른쪽 노드의 왼쪽과 오른쪽을 방문한다.

즉, 현재 노드를 방문할 때 현재 노드의 왼쪽과 오른쪽 노드를 차례로 큐에 넣어 둔다. 그리고, 큐에서 순서대로 꺼내서 같은 방식으로 처리한다. 여기서는 파이썬의 리스트를 Queue로 사용한다.

 

from collections import deque

tree = ["A", "B", "C", "D", "E", "F", None, "G"]

def levelorder(tree):
    if not tree:
        return
    
    queue = deque([0])

    while queue:
        parent = queue.popleft()
        
        print(tree[parent], end=" ")

        left, right = 2*parent + 1, 2*parent + 2

        if left < len(tree) and tree[left] is not None:
            queue.append(left)
        if right < len(tree) and tree[right] is not None:
            queue.append(right)
            
levelorder(tree) # A B C D E F G