Data-Structures Binary Search Tree Q1 - Level Order Traversal 풀이

* 4/17 발표를 위한 자료

문제 해석 :

트리가 주어졌을 때 노드들을 level별로 출력하라.

 

이 문제를 풀기 전에 두 가지 생각이 들었다.

1. 왜 큐를 사용하라고 했나?

2. 재귀호출로도 구현 가능?

 

이전 문제를 풀 때는 현재 노드의 자식 노드를 방문할 때 재귀 호출을 주로 사용했다.

-> 자식 노드의 자식 노드로 깊이 탐색을 하여 base case에 다다르면 재귀 호출을 종료하는 식으로 top-down 구현

 

그런데 이번 문제에서는 너비 탐색을 해야 해서 재귀를 쓰면 안 된다.

그럼 현재 노드의 자식 노드를 어떻게 방문?

-> 큐에 같은 레벨의 노드들을 한꺼번에 넣어두고

-> 큐에서 하나씩 꺼내면서 그 노드의 자식 노드를 또 다시 큐에 넣기

-> 이 과정을 반복하면 큐의 FIFO 성질에 의해 같은 레벨의 노드들을 먼저 방문할 수 있게 된다.

 

구현 과정 :

작성한 코드 :

void levelOrderTraversal(BSTNode* root)
{
	Queue* q = (Queue*)malloc(sizeof(Queue)); //큐 생성
	enqueue(q->head, q->tail, root); //큐에 root 삽입

	while(q->head!=NULL){ //큐가 빌 때까지 실행
		BSTNode* node = dequeue(q->head, q->tail); //큐에서 노드 하나 꺼내기
		printf("%d ", node->item);
		
		//꺼낸 노드의 자식 노드를 left, right 순서대로 큐에 넣기
		if(node->left != NULL) enqueue(q->head, q->tail, node->left);
		if(node->right != NULL) enqueue(q->head, q->tail, node->right);
	}

}

 

런타임 에러?

 

원인 분석 :

enqueue(), dequeue() 호출부에서 에러가 발생

인자 전달에 문제가 있는 것으로 판단되어 구조체 형태와 함수 프로토타입을 확인함

typedef struct _QueueNode {
	BSTNode *data;
	struct _QueueNode *nextPtr;
}QueueNode; 

typedef struct _queue
{
	QueueNode *head;
	QueueNode *tail;
}Queue;


void enqueue(QueueNode **headPtr, QueueNode **tailPtr, BSTNode *node);
BSTNode* dequeue(QueueNode **headPtr, QueueNode **tailPtr);

q->head, q->tail은 포인터 타입이므로 이러한 오류가 발생

따라서 &(q->head), &(q->tail)로 수정해야 한다.

 

완성된 코드 :

void levelOrderTraversal(BSTNode* root)
{
	Queue* q = (Queue*)malloc(sizeof(Queue)); //큐 생성
	enqueue(&(q->head), &(q->tail), root); //큐에 root 삽입

	while(q->head!=NULL){ //큐가 빌 때까지 실행
		BSTNode* node = dequeue(&(q->head), &(q->tail)); //큐에서 노드 하나 꺼내기
		printf("%d ", node->item);
		
		//꺼낸 노드의 자식 노드를 left, right 순서대로 큐에 넣기
		if(node->left != NULL) enqueue(&(q->head), &(q->tail), node->left);
		if(node->right != NULL) enqueue(&(q->head), &(q->tail), node->right);
	}

}

 

재귀 호출이 안 되는 이유?

void levelOrderTraversal(BSTNode* root){

	printf("%d ", root->item);
	
	levelOrderTraversal(root->left);
	levelOrderTraversal(root->right);

}

재귀 호출은 코드가 이런 식으로 짜여지는데, 왼쪽 노드 탐색이 리프노드에 도달할 때까지 계속 재귀호출한다.

-> 깊이 탐색을 하게 되므로 같은 level에 있는 노드들을 먼저 읽지 못함

 

즉 이 함수는 BFS 탐색을 요구하고 있고 너비 우선 탐색을 할 때는 큐를 사용해야 하는 이유를 알게 되었다.

반면 DFS 탐색 즉 깊이 탐색을 할 때는 재귀 함수 또는 스택을 사용해야 한다는 사실을 알 수 있다.

 

Note:

문제에서 요구하는 것이 level order traversal이었음에도 바로 bfs 탐색이고 큐를 사용해야겠다는 생각이 들지 않은 걸 보면

내가 알고리즘주차 때 완전탐색을 깊이 있게 이해하지 않았구나 하는 생각이 들었다.

 

bfs는 인접한 곳 부터 방문이니까 큐, dfs는 깊이 탐색이니까 스택이라는 정도만 어렴풋이 이해하고 있었고

구현할 때는 그냥 기계적으로 bfs는 큐, dfs는 스택을 사용했다는 것을 깨달았다.

 

이번 문제 풀이를 통해 트리(또는 그래프)에서 완전탐색을 할 때 왜 스택(재귀)과 큐를 써야 하는지에 대해 와닿았다.