[자료구조&알고리즘] 이진트리(2)

※ 이진트리 - 넓이 우선 순회(Breadth first traversal)

- 원칙 : 수준(level)이 낮은 노드를 우선으로 방문

같은 수준의 노드들 사이에서는 부모 노드의 방문 순서에 따라 방문하고

왼쪽 자식 노드를 오른쪽 자식보다 먼저 방문함 => 재귀적 방식과 적합하지 않음

 

한 노드를 방문했을 때, 나중에 방문할 노드들을 순서대로 기록해 두어야함 => 큐(queue)를 이용해 보자

 

1. (초기화) traversal <- 빈 리스트, q <- 빈 큐

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

3. q가 비어 있지 않을 때

 > node <- q 에서 원소를 추출

 > node 방문

 > node 왼쪽, 오른쪽 자식들을 q에 추가 (존재할 경우만)

4. q가 빈 큐가 되면 모든 노드를 방문한 것으로 생각한다