[C]트리 레벨 순회 - Level Order Traverse

: 각 노드를 레벨 순으로 탐색하는 방법으로 큐 (너비우선탐색, BFS) 이용하여 구현

#define _CRT_SEUCRE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>

#define SIZE 128

typedef struct _TREENODE_ {
	char data;
	struct _TREENODE_* left;
	struct _TREENODE_* right;
}TREENODE;


void deleteTree(TREENODE* node) {
	if (node == NULL) {
		return;
	}
	else {
		deleteTree(node->left);
		deleteTree(node->right);
		free(node);
		node = NULL;
	}
}

TREENODE* makeRootNode(char data, TREENODE* left, TREENODE* right) {
	TREENODE* root = (TREENODE*)calloc(1, sizeof(TREENODE));
	assert(root != NULL);
	root->data = data;
	root->left = left;
	root->right = right;

	return root;
}

typedef struct _Q_NODE_ {
	TREENODE* node;
	struct _Q_NODE_* link;
}Q_NODE;

typedef struct _Q_TYPE_ {
	Q_NODE* front;
	Q_NODE* rear;
	bool visited[SIZE];
}Q_TYPE;

Q_TYPE* makeQueue() {
	Q_TYPE* queue = (Q_TYPE*)calloc(1, sizeof(Q_TYPE));
	assert(queue != NULL);
	
	return queue;
}

int IsEmpty(Q_TYPE* q) {
	return q->front ==NULL ;
}

void EnQueue(Q_TYPE* q,TREENODE * node) {
	Q_NODE* newNode = (Q_NODE*)calloc(1, sizeof(Q_NODE));
	assert(newNode != NULL);

	newNode->node = node;
	newNode->link = NULL;

	if (IsEmpty(q)) {
		q->front = newNode;
		q->rear = newNode;
	}
	else {
		q->rear->link = newNode;
		q->rear = newNode;
	}
}

TREENODE* DeQueue(Q_TYPE* q) {
	if (IsEmpty(q)) {
		return;
	}
	else {
		Q_NODE* delNode = q->front;
		TREENODE* Node = q->front->node;
		q->front = delNode->link;
		free(delNode);
		delNode = NULL;

		return Node;
	}
}

void levelorderTraverse(TREENODE* node) {
	Q_TYPE* queue = makeQueue();

	EnQueue(queue, node);
	queue->visited[node->data - '\0'] = true;
	while (queue) {
		TREENODE* now = DeQueue(queue);
		
		printf("%c ", now->data);


		
		TREENODE* left = now->left;
		TREENODE* right = now->right;

		if (left != NULL) {
			
			if (queue->visited[left->data - '\0'] == false) {
				queue->visited[left->data - '\0'] = true;
				EnQueue(queue, left);
			}
			
		}
		if (right != NULL) {
			if (queue->visited[right->data - '\0'] == false) {
				queue->visited[right->data - '\0'] = true;
				EnQueue(queue, right);
			}
		}

	}
}


int main() {
	TREENODE* n7 = makeRootNode('D', NULL, NULL);
	TREENODE* n6 = makeRootNode('C', NULL, NULL);
	TREENODE* n5 = makeRootNode('B', NULL, NULL);
	TREENODE* n4 = makeRootNode('A', NULL, NULL);
	TREENODE* n3 = makeRootNode('/', n6, n7);
	TREENODE* n2 = makeRootNode('*', n4, n5);
	TREENODE* n1 = makeRootNode('-', n2, n3);

	

	printf("\nlevelorder : ");
	levelorderTraverse(n1);

	deleteTree(n1);




	getchar();
	return 0;
}

 

 

 

cf. 간단한 버전

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <memory.h>

#define MAX_SIZE 100
#define TRUE	1
#define FALSE	0

//#define TRAVERSE_DEBUG

typedef int NodeData;

typedef struct _TREENODE_ {
	NodeData data;
	struct _TREENODE_* left;
	struct _TREENODE_* right;
}TREENODE;

typedef struct _NODEMAP_ {
	int flag;
	NodeData data;
}NODEMAP;

TREENODE * queue[MAX_SIZE];
int front = -1;
int rear = -1;

int isEmpty() {
	return front == rear;
}

int isFull() {
	return rear == MAX_SIZE - 1;
}

void enQueue(TREENODE* item) {
	if (!isFull()) {
		queue[++rear] = item;
	}
}

TREENODE* deQueue() {
	if (!isEmpty()) {
		return queue[++front];
	}
}

void levelOrder(TREENODE * root) {
	enQueue(root);
	while (!isEmpty()) {
		TREENODE * data = deQueue();
		printf("%c ", data->data);
		enQueue(data->left);
		enQueue(data->right);
	}
}


int getMax(int a, int b)
{
	return ((a > b) ? a : b);
}

int countNode(TREENODE* node) {
	if (node == NULL) {
		return 0;
	}
	else {
		return 1 + countNode(node->left) + countNode(node->right);
	}
}

int getHeight(TREENODE* node) {
	if (node == NULL) {
		return 0;
	}
	else {
		return 1 + max(getHeight(node->left), getHeight(node->right));
	}
}

void printGivenLevel(TREENODE* root, int level, NODEMAP* map, int pos)
{
	if (root == NULL)
	{
		return;
	}
	if (level == 1) {
		map[pos].data = root->data;
		map[pos].flag = TRUE;
	}
	else if (level > 1)
	{
		printGivenLevel(root->left, level - 1, map, pos * 2);
		printGivenLevel(root->right, level - 1, map, pos * 2 + 1);
	}
}

void showTree(TREENODE* node)
{
	int height = 0;
	int numOfNodes = 0;
	NODEMAP* treeArray = NULL;
	char** square = NULL;
	static int pos = 0;
	int cnt_i;
	int cnt_j;
	int position;
	int start, term, index;

	height = getHeight(node);
	if (height != 0) {
		numOfNodes = (1 << height);
	}
	treeArray = (NODEMAP*)calloc(numOfNodes, sizeof(NODEMAP));
	assert(treeArray != NULL);

	square = (char**)calloc(height, sizeof(char*));
	for (cnt_i = 0; cnt_i < height; cnt_i++)
	{
		square[cnt_i] = (char*)calloc(numOfNodes, sizeof(char));
		memset(square[cnt_i], '.', numOfNodes);
	}

	// level order 순으로 treeArray에 노드의 데이터 삽입
	pos = 1;
	for (cnt_i = 1; cnt_i <= height; cnt_i++) {
		printGivenLevel(node, cnt_i, treeArray, pos);
	}

	// 한칸씩 왼쪽으로 이동
	for (cnt_i = 1; cnt_i <= numOfNodes; cnt_i++)
	{
		treeArray[cnt_i - 1] = treeArray[cnt_i];
	}

	pos = 0;
	start = (1 << (height - 1)) - 1;
	term = (1 << (height));
	index = (1 << (height - 2));
	for (cnt_i = 0; cnt_i < height; cnt_i++)
	{
		for (cnt_j = start; cnt_j < numOfNodes; cnt_j += term)
		{
			if (treeArray[pos].flag == TRUE) {
				if (treeArray[pos].data >= 0 && treeArray[pos].data <= 9) {
					square[cnt_i][cnt_j] = (treeArray[pos].data + '0');
				}
				else {
					square[cnt_i][cnt_j] = (treeArray[pos].data);
				}
			}
			else {
				square[cnt_i][cnt_j] = '.';
			}
			pos += 1;
		}
		term >>= 1;
		start -= index;
		index >>= 1;
	}

	printf("\n");
	for (cnt_i = 0; cnt_i < height; cnt_i++)
	{
		for (cnt_j = 0; cnt_j < numOfNodes; cnt_j++)
		{
			printf("%c", square[cnt_i][cnt_j]);
		}
		printf("\n");
	}

	if (treeArray != NULL) {
		free(treeArray);
	}
	if (square != NULL)
	{
		for (cnt_i = 0; cnt_i < height; cnt_i++)
		{
			if (square[cnt_i] != NULL)
			{
				free(square[cnt_i]);
			}
		}
		free(square);
	}
}

TREENODE* makeRootNode(NodeData data, TREENODE* leftNode, TREENODE* rightNode)
{
	TREENODE* root = (TREENODE*)calloc(1, sizeof(TREENODE));
	assert(root != NULL);
	root->data = data;
	root->left = leftNode;
	root->right = rightNode;

	return root;
}

void makeLeftSubTree(TREENODE* root, TREENODE* leftSub)
{
	root->left = leftSub;

}

void makeRightSubTree(TREENODE* root, TREENODE* rightsub)
{
	root->right = rightsub;
}

NodeData getData(TREENODE* node)
{
	return node->data;
}

void setData(TREENODE* node, NodeData data)
{
	node->data = data;
}

TREENODE* getLeftSubTree(TREENODE* node)
{
	return node->left;
}

TREENODE* getRightSubTree(TREENODE* node)
{
	return node->right;
}

void preorderTraverse(TREENODE* node)
{
	if (node != NULL) {
		printf("%c ", node->data);
		preorderTraverse(node->left);
		preorderTraverse(node->right);
	}
}

void inorderTraverse(TREENODE* node)
{	
	if (node != NULL) {
		inorderTraverse(node->left);
		printf("%c ", node->data);
		inorderTraverse(node->right);
	}
}

void postorderTraverse(TREENODE* node)
{
	if (node != NULL) {
		postorderTraverse(node->left);
		postorderTraverse(node->right);
		printf("%c ", node->data);
	}
}

void deleteTree(TREENODE* node)
{
	if (node == NULL) {
		return;
	}
	else {
		deleteTree(node->left);
		deleteTree(node->right);

		printf("del tree data: %c\n ", node->data);
		free(node);
	}
}

int main()
{
	TREENODE* n7 = makeRootNode('D', NULL, NULL);
	TREENODE* n6 = makeRootNode('C', NULL, NULL);
	TREENODE* n5 = makeRootNode('B', NULL, NULL);
	TREENODE* n4 = makeRootNode('A', NULL, NULL);
	TREENODE* n3 = makeRootNode('/', n6, n7);
	TREENODE* n2 = makeRootNode('*', n4, n5);
	TREENODE* n1 = makeRootNode('-', n2, n3);


	printf("\n");

	showTree(n1);

	printf("\n preorder : \n");
	preorderTraverse(n1);

	printf("\n inorder : \n");
	inorderTraverse(n1);

	printf("\n postorder :\n");
	postorderTraverse(n1);



	printf("\n levelorder :\n");
	levelOrder(n1);

	printf("\n");
	deleteTree(n1);

	getchar();


	getchar();
	return 0;
}