코드 7-8

def levelorder(cur):
    q = Queue()

    q.put(cur)
    while not q.empty():
        cur = q.get()
        # 방문
        print(cur.data, end=' ')
        # 현재 노드의 왼쪽 자식이 있다면
        # 큐에 추가
        if cur.left:
            q.put(cur.left)
        # 현재 노드의 오른쪽 자식이 있다면
        # 큐에 추가
        if cur.right:
            q.put(cur.right)

코드 7-8을 보면 코드가 BFS와 매우 유사하다는 것을 알 수 있습니다. BFS 일종이므로 당연한 것이지요. 부모부터 방문하고 다음 레벨로 이동하므로 방문을 확인할 수 있는 배열은 필요하지 않습니다. 트리의 차수가 2이므로 adj[cur]={cur.left, cur.right}겠지요. 먼저 왼쪽 자식이 있는지 확인하고 있다면 큐에 삽입합니다. 다음 오른쪽 자식이 있는지 확인하고 있다면 큐에 삽입합니다. 이렇게 큐가 빌 때까지 반복하면 레벨이 깊어지면서 모든 노드를 방문하게 됩니다.

이 장에서는 일반적인 트리의 특징과 트리에서 순회를 자세히 알아보았습니다. 다음 장부터 트리의 다양한 예를 살펴볼 것입니다. 먼저 자료 구조에서 아주 중요한 위치를 차지하고 있는 이진 탐색 트리를 알아보겠습니다.