이진 트리의 넓이 우선 순회 (BFS; Breadth First Traversal)

이진 트리의 넓이 우선 순회 (BFS: Breadth First Traversal)

원칙

• 수준(Level)이 낮은 노드를 우선으로 방문
• 같은 수준의 노드를 사이에는 부모 노드의 방순 순서에 따라 방문(왼 > 오)

순회의 결과: A -> B -> C -> D -> E … J

넓이 우선 순회 흐름 설계

• 수준이 낮은 노드 부터 방문해서 큐에 enqueue

• A를 방문함(A를 dequeue)

• A의 자식노드 왼쪽 → 오른쪽 으로

• B를 방문(B를 dequeue)

• B의 자식노드(E)를 enqueue

• C를 방문(C를 dequeue)

• C의 자식노드(G)를 enqueue

• D를 방문(D를 dequeue)

• D의 자식노드(H)를 enqueue

• E를 방문(E를 dequeue), E의 자식노드는 없음

• F를 방문(F를 dequeue)

• F의 자식노드(I)를 enqueue

• G를 방문(G를 dequeue), G의 자식노드 없음

• H를 방문(H를 dequeue), H의 자식노드 없음

• I를 dequeue(I를 방문), I의 자식노드 없음, 큐가 비어있으면 순회 끝.

넓이 우선 순회 알고리즘 구현

1. traversal에는 빈 리스트를 초기화, q에는 빈 큐를 초기화한다.
2. 빈 트리가 아니면, root node를 큐에 추가(enqueue)한다
3. q가 비어있지 않는 동안
   1. q의 원소를 추출하여(dequeue) node에 저장한다
   2. node를 방문 처리(traversal에 append)한다
   3. node의 왼쪽, 오른쪽 자식 노드가 있으면 q에 추가한다
4. q가 비어있는 큐가 되면 모든 노드 방문 완료하였음으로 traversal를 리턴한다