学步园

#include<stdio.h>
#include<stdlib.h>
#include<queue>
using namespace std;
typedef struct TNode{
	int value;
	struct TNode* left;
	struct TNode* right;	
}Node;
int num[1008];
int cmp(const void *atmp,const void *btmp){
	int* a=(int*)atmp;
	int* b=(int*)btmp;
	return *a-*b;
}
/*根据给定的层计算从0层到level总共的节点（1+2+4+...）*/ 
int calTotal(int level){
	int i,j,total=0,tmp;
	for(i=0;i<=level;i++){
		tmp=1;
		for(j=0;j<i;j++){
			tmp=tmp*2;
		}
		total=total+tmp;	
	}
	return total;
}
/*根据给定的节点总数计算树的层数，层数从0开始，返回的是树的深度-1（考虑到buildTree的计算方式）*/
int calLevel(int total){ 
	int i,j,sum=0,tmp;
	for(i=0;;i++){
		tmp=1;
		for(j=0;j<i;j++){
			tmp=tmp*2;
		}
		sum=sum+tmp;
		if(sum>=total) break;
	}
	return i-1;
}
/*
buildTree(int s,int e)其中s从0开始；
level为能构成的完全2叉搜索树的实际层数-1；
totalpre为前level（0,1,2....level）的总节点树； 
totalcur为前level+1的总节点树； 
想法是：前level上属于左子树的节点有totalpre/2。
用给定的节点数nodes=e-s+1，减去totalpre，那么剩下的节点肯定在下一层。
那么关键就是就算level+1层上有多少个节点属于左子树，而这点通过if语句就可以知道。 
*/
Node* buildTree(int s,int e){
	if(e-s<0){
		return NULL;
	}
	if(e-s==0){
		Node* node=(Node*)malloc(sizeof(Node));
		node->value=num[s];
		node->left=NULL;
		node->right=NULL;
		return node;
	}
	int level=calLevel(e-s+1); 
	int totalpre=calTotal(level);
	int totalcur=calTotal(level+1);
	int diff=totalcur-totalpre;
	int nodes=e-s+1;
	int leftChilds=totalpre/2;
	if((nodes-totalpre)<diff/2)
		leftChilds=leftChilds+(nodes-totalpre);
	else 
		leftChilds=leftChilds+diff/2;
	Node* node=(Node*)malloc(sizeof(Node));
	node->value=num[s+leftChilds];
	node->left=buildTree(s,s+leftChilds-1);
	node->right=buildTree(s+leftChilds+1,e);
	return node;

}
/*按照先序遍历打印树用作建树测试*/ 
void printTreePreOrder(Node* node){ 
	if(node==NULL) return;
	printf("%d ",node->value);
	printTreePreOrder(node->left);
	printTreePreOrder(node->right);
}
/*按照层次遍历打印树 */
void printTreeLevelOrder(Node* node){
	queue<Node*> qu;
	while(!qu.empty()){
		qu.pop();
	}
	printf("%d",node->value);
	if(node->left!=NULL) qu.push(node->left);
	if(node->right!=NULL) qu.push(node->right);
	while(!qu.empty()){
		Node* tmp=qu.front();
		qu.pop();
		printf(" %d",tmp->value);
		if(tmp->left!=NULL) qu.push(tmp->left);
		if(tmp->right!=NULL) qu.push(tmp->right);
	}
	printf("\n");
}
/*回收树的内存*/ 
void Delloc(Node* node){
	if(node==NULL) return;
	Delloc(node->left);
	Delloc(node->right);
	free(node);
}
int main(){
	int i,j,n;
	scanf("%d",&n);
	for(i=0;i<n;i++){
		scanf("%d",&num[i]);
	}
	qsort(num,n,sizeof(int),cmp);
	Node* root=buildTree(0,n-1);
	printTreeLevelOrder(root);
	Delloc(root);
	return 0;
}