트리의 순회의 응용(레벨 순회)

트리의 기본적인 순회방법중 전위,중위,후위순회는 코드작성이 쉽고 단순해서 이해가 쉽습니다.

(엄밀히 말해서, 쉽다기보다는 외우기쉽기 때문에)

트리의 순회의 응용으로써, 레벨(level)순회가 있습니다. 레벨순회는 루트 노드부터, 마지막 노드까지 순회하되, 왼쪽부터 오른쪽순으로 순회합니다.

트리는 사이클없는 그래프인데, 직접 트리를 그려서 bfs연산을 해보시면 알겠지만, 제가 말씀드린 왼쪽->오른쪽 순으로 가까운순으로 레벨순회를 합니다. 즉, 레벨순회는 bfs기반의 탐색(순회)방법이라고 할 수 있습니다. 

트리의 구조체를 담을 수 있는 큐를 선언하고, 큐에 루트노드를 삽입 한 후 bfs처럼 연산을 수행하면됩니다. bfs와의 차이점은 bfs는 한번 탐색한 방향은 다시 안가기 때문에, 이를 나타내기위해 visited배열을 선언하지만, 트리순회는 현재 노드의 왼쪽자식노드,오른쪽노드의 유무를 탐색하며 오직 순회만 하기때문에 상관이없습니다. 결국 한번 방문하는것은 똑같습니다.

코드를 보면 이해가 쉽습니다. 저는 트리를 담을 큐를 원형큐로 선언하였습니다.

코드

#include<cstdio>
#include<cstring>
#include<cstdlib>
typedef struct treeNode {
	char data;
	struct treeNode* left;
	struct treeNode* right;
}treeNode;
typedef struct {
	treeNode* queue[100];
	int front, rear;
}QNode;
void level_order(treeNode*root);
void init(QNode* q)
{
	q->front = q->rear = 0;
}
int is_empty(QNode* q)
{
	return q->front == q->rear;
}
int is_full(QNode* q)
{
	return (q->rear + 1) % 100 == q->front;
}
void enqueue(QNode* q, treeNode* root)
{
	if (is_full(q))
		return;

	q->rear = (q->rear + 1) % 100;
	q->queue[q->rear] = root;
}
treeNode* dequeue(QNode* q)
{
	if (is_empty(q))
		exit(1);
	else
	{
		q->front = (q->front + 1) % 100;
		return q->queue[q->front];
	}
}
int main()
{
	treeNode ptr1 = { 'a',NULL,NULL }; treeNode ptr2 = { 'b',NULL,NULL };
	treeNode ptr3 = { 'c',NULL,NULL }; treeNode ptr4 = { 'd',NULL,NULL };
	treeNode ptr5 = { '*',&ptr1,&ptr2 }; treeNode ptr6 = { '/',&ptr3,&ptr4 };
	treeNode ptr7 = { '+',&ptr5,&ptr6 };
	treeNode* root = &ptr7;
	level_order(root);
	puts("");

}
void level_order(treeNode* root)
{
	QNode q;
	init(&q);
	if (root == NULL)return;
	enqueue(&q,root);
	while (!is_empty(&q))
	{
		root = dequeue(&q);
		printf("%c ", root->data);
		if (root->left)
			enqueue(&q, root->left);
		if (root->right)
			enqueue(&q,root->right);
	}
}

결과