2.3.3 연습 문제 8: 레벨 순서 순회 구현하기
이번 연습 문제에서는 연습 문제 7에서 만들었던 조직도 트리에 대해 레벨 순서 순회를 구현해보겠습니다. 다른 트리 순회 방법과는 달리 레벨 순서 순회 방법은 현재 노드에 직접 연결되지 않은 노드로 이동합니다. 이러한 경우 재귀를 사용하지 않고 구현하는 것이 더 쉽습니다. 트리를 구성하는 부분은 연습 문제 7의 코드를 그대로 사용하겠습니다.
1. 연습 문제 7에서 구현한 org_tree 구조체 안에 다음 함수를 추가합니다.
static void levelOrder(node* start)
{
if (!start)
return;
std::queue<node*> q;
q.push(start);
while (!q.empty())
{
int size = q.size();
for (int i = 0; i < size; i++)
{
auto current = q.front();
q.pop();
std::cout << current->position << ", ";
if (current->first)
q.push(current->first);
if (current->second)
q.push(current->second);
}
std::cout << std::endl;
}
}
위 소스 코드는 먼저 루트 노드를 방문하고, 그다음에 자식 노드를 방문합니다. 자식 노드를 방문할 때 해당 노드의 자식 노드를 모두 큐에 추가합니다. 그래서 현재 레벨의 모든 노드 방문이 끝나면 큐에 저장된 노드를 꺼내어 방문합니다. 즉, 현재 레벨의 노드를 방문할 때 다음 레벨 노드를 미리 큐에 추가하는 방식입니다. 이러한 작업을 큐가 완전히 빌 때까지 반복하면 레벨 순서 순회가 완료됩니다.