넓이 우선 순회(Breadth First Traversal)

넓이 우선 순회(BFS)의 원칙은 수준(level)이 낮은 노드를 우선적으로 방문하는 것이다.

같은 수준의 노드들 사이에서는 부모 노드의 방문 순서에 따라 방문하며, 왼쪽 자식 노드를 오른쪽 자식보다 먼저 방문한다는 원칙이 적용된다.

BFS를 구현하고자 할 경우, DFS에서 활용하였던 재귀적 방법(Recursive)이 적합하지 않다.

BFS는 한 노드를 방문했을 때, 나중에 방문할 노드들을 순서대로 기록해 두어야 한다. 이러한 성질 때문에 BFS를 구현할 때에는 큐(Queue)를 이용하는 것이 편리하다.

노드를 방문(큐에서 원소를 뽑는다)하였을 때 자식 노드가 존재한다면 왼쪽 자식부터 순서대로 큐에 넣어주면 된다. 그리고 큐에서 원소를 하나 뽑고, 그 원소에 방문한다. 이러한 과정을 큐가 비워질 때까지 반복한다.


구현

BFS는 DFS와는 다르게 재귀적인 방법을 사용하는 것이 아니므로, BinaryTree 클래스에 def bft(self): 메소드만 구현해주면 된다. 알고리즘은 다음과 같다.

  1. (초기화) traversal에 빈 리스트, q에 빈 큐를 만들어준다.

  2. 빈 트리가 아니면, root node를 q에 추가해준다.(enqueue)

  3. q가 비어 있지 않은 동안, q에서 원소를 추출(dequeue)하여 node에 저장한다. 그리고 그 node를 방문한다. node의 왼쪽/오른쪽이 존재한다면 이들을 q에 추가해 준다.

  4. q가 빈 큐가 되면 모든 노드 방문을 완료한다.