코딩무식자 전공생

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

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

트리의 순회의 응용으로써, 레벨(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);
	}
}

결과

자료구조의 트리 단원을 배우고 나서 응용할 수 있는 몇가지 연산들을 한 코드에 담아봤습니다.

후위 연산, 노드의 갯수, 단말노드의 갯수, 트리의높이를 구하는 코드입니다.

재귀함수를 이해하고 응용할 수 있어야함을 알 수 있습니다.

소스코드는 아래 그림과 같이 트리가 이루어져 있을 때를 가정합니다.

코드

#include<cstdio>
#include<cstring>
#include<cstdlib>
#define max(a,b) (((a)>(b))?(a):(b))
typedef struct treeNode
{
	int data;
	struct treeNode* left;
	struct treeNode* right;
}treeNode;

treeNode n5 = { 0,NULL,NULL };
treeNode n4 = { 1,NULL,NULL };
treeNode n3 = { 2,NULL,NULL };
treeNode n2 = { 3,&n4,&n5 };
treeNode n1 = { 4,&n2,&n3 };
treeNode* root = &n1;
int cal_post(treeNode* root)
{
	int left, right;
	if (root)
	{
		left = cal_post(root->left);
		right = cal_post(root->right);
		return root->data + left + right;
	}
	return 0;
}
int node_count(treeNode* root)
{
	int count = 0;
	if (root)
	{
		count = 1+node_count(root->left) + node_count(root->right);
	}
	return count;
}
int leaf_node(treeNode* root)
{
	int count = 0;
	if (root)
	{
		if (root->left==NULL && root->right==NULL)
		{
			return 1;
		}
		else
		{
			return leaf_node(root->left) + leaf_node(root->right);
		}
	}
	return count;
}
int height(treeNode* root)
{
	int hight = 0;
	int left, right;
	if (root)
	{
		left = height(root->left);
		right = height(root->right);
		return 1+max(left, right);
	}
	return hight;
}
int main()
{
	printf("후위덧셈!!\n%d\n", cal_post(root));
	printf("노드의갯수!!!\n%d\n", node_count(root));
	printf("단말노드의갯수!!\n%d\n", leaf_node(root));
	printf("트리의높이는!!\n%d\n", height(root));
}

결과