[C] 학교과제_황제노드찾기

학교과제로 풀었던 황제노드찾기. 내부노드를 한 번 씩만 방문해 황제노드를 판별하는 방식이다. 순회 방식은 레벨순회이다.

황제노드 - 자신은 로만노드가 아니지만 자기 아래 자손들이 모두 로만노드인 노드

로만노드 - 자신의 오른쪽과 왼쪽 부트리의 노드 개수 차이가 5 이하인 노드

구글링 해도 황제, 로만노드의 개념이 나오지 않는 것을 보면 교수님이 고안해내신 개념인 것 같다.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

typedef struct node {

	struct node *left;
	struct node *right;

}NODE;

typedef struct {

	NODE *root;

}TREE;

// 각 노드의 좌,우 자식 유무에 대한 정보를 담은 함수. initNode를 편리하게 하기 위함
// 예를 들어, NODE_INFO[0][0] == 1 이면 0번(root) 노드의 왼쪽 자식이 있는 것이다.
// NODE_INFO[노드번호][자식번호] 노드번호 0 ~ 28, 자식번호 0 = left, 1 = right
// 노드의 번호는 root부터 선위순회 방문 순서대로 부여했다.
int NODE_INFO[29][2] = { { 1,1 },{ 1,1 },{ 1,1 },{ 1,1 },{ 0,0 },{ 1,1 },{ 0,0 },{ 1,1 },{ 1,1 },{ 0,0 },{ 0,0 },{ 0,0 },{ 0,0 },{ 1,1 },{ 1,1 },{ 0,0 },{ 0,0 },{ 1,1 },{ 0,0 },{ 0,0 },{ 1,1 },{ 0,0 },{ 1,1 },{ 1,1 },{ 0,0 },{ 0,0 },{ 1,1 },{ 0,0 },{ 0,0 } };
int NOW_NODE_NUM = 0;

// 큐 관련 변수
NODE *queue[15];
int front = 0, rear = 0;
int MAX = 15;

// 트리 관련 함수
NODE* initTree();
void linkNode(NODE *, int, int);
NODE* getNode();

int isEmperor(NODE *);
int isRoman(NODE *);

int isExternal(NODE *);

void levelSearch(NODE *);

// 큐 관련 함수
void enQueue(NODE *);
NODE* deQueue();
int isEmpty();
int isFull();

int main() {

	TREE t;

	t.root = initTree();

	levelSearch(t.root);

	return 0;

}

NODE* initTree() {

	NODE* root = getNode();

	linkNode(root, NODE_INFO[NOW_NODE_NUM][0], NODE_INFO[NOW_NODE_NUM][1]);

	return root;

}

void linkNode(NODE *n, int left, int right) {

	if (left != 0) {
		n->left = getNode();
	}
	if (right != 0) {
		n->right = getNode();
	}

	if (n->left != NULL) {
		linkNode(n->left, NODE_INFO[++NOW_NODE_NUM][0], NODE_INFO[NOW_NODE_NUM][1]);
	}
	if (n->right != NULL) {
		linkNode(n->right, NODE_INFO[++NOW_NODE_NUM][0], NODE_INFO[NOW_NODE_NUM][1]);
	}

}

NODE* getNode() {

	NODE *new_node;

	new_node = (NODE *)malloc(sizeof(NODE));

	new_node->left = NULL;
	new_node->right = NULL;

	return new_node;

}

int isEmperor(NODE *n) {

	int left = 0, right = 0;

	left = isRoman(n->left);
	right = isRoman(n->right);

	if (left == 0) return 0;
	else if (right == 0) return 0;
	else if (abs(left - right) <= 5) return 0;

	return 1;

}

int isRoman(NODE *n) {

	int left, right;

	if (isExternal(n)) {
		return 1;
	}

	left = isRoman(n->left);
	if (left == 0) {
		return 0;
	}

	right = isRoman(n->right);
	if ((right > 0) && (abs(left - right) <= 5)) {
		return left + right + 1;	// 부트리의 노드 수 반환
	}
	else
		return 0;

}

int isExternal(NODE *n) {

	return n->left == NULL && n->right == NULL;

}

void levelSearch(NODE *n) {

	NODE *i;
	int count = 1;

	int internal_Count = 0;
	int emperor_Count = 0;

	enQueue(n);

	while (1) {
		i = deQueue();

		if (i == NULL) break;

		internal_Count++;

		if (isEmperor(i)) { printf("%d\t황제노드\n", count); emperor_Count++; }

		if (i->left != NULL && !isExternal(i->left)) enQueue(i->left);
		if (i->right != NULL && !isExternal(i->right)) enQueue(i->right);

		count++;
	}

	printf("방문한 내부 노드 수 %d개, 황제노드 수 %d개\n", internal_Count, emperor_Count);

}


// 이하 큐 관련 함수

void enQueue(NODE *n) {

	if (isFull()) {
		printf("Overflow.\n");
	}

	queue[rear] = n;

	rear = (rear + 1) % MAX;

}

NODE* deQueue() {

	int tmp = front;

	if (isEmpty()) {
		return NULL;
	}

	front = (front++) % MAX;

	return queue[tmp];

}

int isEmpty() {

	return front == rear;

}

int isFull() {

	return ((rear + 1) % MAX) == front;

}