用户:Antigng-bot/test

#include <stdio.h>
#include <malloc.h>
typedef struct _num_node_t
{
	unsigned long long int sum;
	unsigned long long int *part;
} NUM_NODE;
typedef struct _bin_tree_node_t
{
	struct _bin_tree_node_t *father;
	struct _bin_tree_node_t *l;
	struct _bin_tree_node_t *r;
} BIN_TREE_NODE;
typedef struct _link_table_t
{
	int num;
	struct _link_table_t *next;
} LINK_TABLE_NODE;
static NUM_NODE *testgen(unsigned int limit)
{
	unsigned int count=0,node_num=0;
	unsigned long long int sum=0;
	unsigned long long int *ptopart;
	NUM_NODE *node;
	node=(NUM_NODE *)calloc(sizeof(NUM_NODE)*(limit+1),1);
	node[0].sum=node[1].sum=1;
	node[1].part=ptopart=(unsigned long long int *)calloc(sizeof(unsigned long long int)*(2),1);
	ptopart[0]=1;
	for(node_num=2;node_num<limit;node_num++)
	{
		sum=0;
		node[node_num].part=ptopart=(unsigned long long int *)calloc(sizeof(unsigned long long int)*(node_num+1),1);
		for(count=0;count<node_num;count++)
		{
			sum+=node[count].sum*node[node_num-1-count].sum;
			ptopart[count]=sum;
		}
		node[node_num].sum=sum;
	}
	return node;
}
static BIN_TREE_NODE *gensubtree(NUM_NODE *num_list,unsigned int node_num,unsigned long long int offset,BIN_TREE_NODE *father)
{
	unsigned long long int *ptopart=num_list[node_num].part;
	BIN_TREE_NODE *tree_node;
	unsigned int pos=0,pre_pos=0;
	unsigned long long int left_offset,right_offset,new_offset;
	if(node_num==0)
	{
		return NULL;
	}
	else if(node_num==1)
	{
		tree_node=(BIN_TREE_NODE *)calloc(sizeof(BIN_TREE_NODE),1);
		tree_node->father=father;
		return tree_node;
	}
	for(pos=0;pos<node_num;pos++)
	{		
		if(ptopart[pos]>offset) break;
	}
	if(pos==0) new_offset=offset;
	else new_offset=offset-ptopart[pos-1];
	left_offset=new_offset/num_list[node_num-1-pos].sum;
	right_offset=new_offset%num_list[node_num-1-pos].sum;
	tree_node=(BIN_TREE_NODE *)calloc(sizeof(BIN_TREE_NODE),1);
	tree_node->father=father;
	tree_node->l=gensubtree(num_list,pos,left_offset,tree_node);
	tree_node->r=gensubtree(num_list,node_num-1-pos,right_offset,tree_node);
	return tree_node;
}

static BIN_TREE_NODE *genbintree(unsigned int num,NUM_NODE *num_list,unsigned int limit)
{
	unsigned int count=0;
	unsigned long long int sum=0;
	for(count=0;count<limit;count++)
	{
		sum+=num_list[count].sum;
		if(sum>num) break;
	}
	if(count==limit) return NULL;
	else if(count==0) return gensubtree(num_list,0,num,NULL);
	else return gensubtree(num_list,count,num-sum+num_list[count].sum,NULL);
}
static void printtree(BIN_TREE_NODE *tree_node,int start)
{
	if(tree_node==NULL) return;
	if(start!=0) putchar('(');
	printtree(tree_node->l,1);
	putchar('X');
	printtree(tree_node->r,1);
	if(start!=0) putchar(')');	
	return;
}
int main(void)
{
	NUM_NODE *t=0;
	BIN_TREE_NODE *b=0;
	LINK_TABLE_NODE *head=0,*p=0,*n=0;
	int num;
	t=testgen(19);
	scanf("%d",&num);
	while(num!=0)
	{
		if(head==NULL)
		{
			head=(LINK_TABLE_NODE *)calloc(sizeof(LINK_TABLE_NODE),1);
			p=n=head;
			head->num=num;
		}
		else
		{
			p=n;
			n->next=(LINK_TABLE_NODE *)calloc(sizeof(LINK_TABLE_NODE),1);
			n=n->next;
			n->num=num;
		}
		scanf("%d",&num);
	}
	n=head;
	while(n!=NULL)
	{
		b=genbintree(n->num,t,19);
		printtree(b,0);
		n=n->next;
		if(n!=NULL) putchar('\n');
	}
	return 0;
}