파이썬) 이진 트리 넓이 우선 순회 연산

이진 트리의 순회 연산에는 깊이, 넓이 우선 순회 연산이 있다. 이번엔 넓이 우선 순회 연산에 대해 소개하겠다.

 

 

넓이 우선 순회의 원칙

 

• 수준(Level)이 낮은 노드를 우선으로 방문
• 같은 수준의 노드들 사이에는 부모 노드의 방문 순서에 따라 방문하고, 왼쪽 자식노드를 오른쪽 자식노드보다 먼저 방문한다.

그림으로 표현하면 다음과 같다.

 

쉽게 설명하면 같은 수준의 노드를 왼쪽부터 아래로 순회한다고 보면 된다. 위 트리의 순회 순서는 알파벳순으로 A~I가 된다.

 

 

이러한 알고리즘을 코드로 구현하기 위한 설계는 큐를 이용해 설명할 수 있다.

 

1.

맨 처음 루트 노드 A를 읽고 자식노드 B,C를 왼쪽 노드부터 빈 큐에 enqueue()한다.

 

2.

 

다음 B 노드를 읽을 때 B를 큐에서 dequeue()하고 순회 리스트에 읽어들인다. 자식 노드가 존재하면 그 자식 노드도 왼쪽부터 큐에 enqueue()한다. 

 

3.

 

다음 C를 읽을 때 C를 큐에서 dequeue()하고 순회 리스트에 읽어들인다. 마찬가지로 자식 노드가 존재하므로 그 자식 노드도 큐에 enqueue()한다.

 

4.

다음 D를 읽을 때 D를 큐에서 dequeue()하고 순회 리스트에 읽어들인다. 마찬가지로 자식 노드가 존재하자만 왼쪽 노드 H밖에 없으므로 H만 큐에 enqueue()한다.

 

이러한 과정을 계속 거치고 큐가 빈 상태가 되면 트리의 모든 노드를 순회한 것이다. 이를 정리하면 다음과 같다.

 

 

1. 트리의 노드를 읽어들일 빈 리스트, 빈 큐 생성

2. 빈 트리가 아니면, 루트 노드를 빈 큐에 추

3. 큐가 비어 있지 않은 동안 

    3.1 큐에서 원소를 추출한다.

    3.2 그 원소를 리스트에 추가한다.

    3.3 노드의 왼쪽, 오른쪽 자식 노드가 있다면 그들을 큐에 추가한다.

 

위 과정을 코드로 구현하면 다음과 같다.

class BinaryTree:

def bft(self):
        traversal = []   
        q = ArrayQueue()  
        if self.root:   # 트리가 비어있지 않은 경우
            q.enqueue(self.root)
            while not q.isEmpty():
                node = q.dequeue()
                traversal.append(node.data)
                if node.left:
                    q.enqueue(node.left)
                if node.right:
                    q.enqueue(node.right)
        else:  # 트리가 빈 트리인 경우
            traversal = []  
            
        return traversal