재귀로 이진 트리 생성, level order로 traversal

과제#14 (만점: 10 점)
양의 정수 n (n > 0) 을 scanf_s 로 입력 받은 뒤, recursive function 을 이용하여 linked representation 으로 다음
규칙에 따라 binary tree 를 구성한 뒤, level order traversal 결과를 화면 출력하라.

• data 값이 n 인 root node 를 생성한다.
• root 를 포함하여 tree 내의 모든 node 에 대해, node N 의 data 값이 k 이면, N 의 left child 는 k*2 를, N 의 right child 는 k+2 를 data 값으로 갖게 한다.
• node 의 data 값 k 가 k>5 이면 leaf node 가 되도록 (child 를 갖지 않도록) 처리한다.

#include <iostream>
#define MAX_QUEUE_SIZE 100

typedef struct treeNode* treePointer;
typedef struct treeNode {
	int data;
	treePointer leftChild, rightChild;
};
treePointer queue[MAX_QUEUE_SIZE];

int front = 0, rear = 0;

treePointer recur(treePointer ptr) {
	treePointer leftNode, rightNode;

	leftNode = (treePointer)malloc(sizeof(*leftNode));
	rightNode = (treePointer)malloc(sizeof(*rightNode));

	if (ptr->data >5 ) {	
		ptr->leftChild = NULL; ptr->rightChild = NULL;
		return ptr;
	}
	leftNode->data = ptr->data * 2; //node의 데이터에 ptr->data*2값 넣음
	ptr->leftChild = recur(leftNode); 

	rightNode->data = ptr->data + 2;
	ptr->rightChild = recur(rightNode); 

	return ptr;
}
void addq(treePointer ptr) { //enqueue
	queue[rear++] = ptr;
}

treePointer deleteq() { //dequeue
	return queue[front++];
}

void levelOrder(treePointer ptr) {
	::front = 0; ::rear = 0;
	if (!ptr) return; //empty tree
	addq(ptr);
	for (;;) {
		ptr = deleteq();
		if (ptr) {
			printf("%d ", ptr->data);
			if (ptr->leftChild) {
				addq(ptr->leftChild);
			}
			if (ptr->rightChild) {
				addq(ptr->rightChild);
			}
		}
		else break;
	}
}
int main() {
	treePointer root, temp;
	root = (treePointer)malloc(sizeof(*root));
	temp = (treePointer)malloc(sizeof(*temp));
	
	scanf_s("%d", &root->data);
	temp = root;
	recur(temp);
	levelOrder(root);
}

이진 트리 생성 후 root부터 enqueue. root dequeue하고 left child, right child enqueue. dequeue하고 자식노드 enqueue 반복하기.